Papers › Random processes for generating task-dependency graphs
Random processes for generating task-dependency graphs
Jesse Geneson, Shen-Fu Tsai
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We investigate random processes for generating task-dependency graphs of order n with m edges and a specified number of initial vertices and terminal vertices. In order to do so, we consider two random processes for generating task-dependency graphs that can be combined to accomplish this task. In the (x, y) edge-removal process, we start with a maximally connected task-dependency graph and remove edges uniformly at random as long as they do not cause the number of initial vertices to exceed x or the number of terminal vertices to exceed y. In the (x, y) edge-addition process, we start with an empty task-dependency graph and add edges uniformly at random as long as they do not cause the number of initial vertices to be less than x or the number of terminal vertices to be less than y. In the (x, y) edge-addition process, we halt if there are exactly x initial vertices and y terminal vertices. For both processes, we determine the values of x and y for which the resulting task-dependency graph is guaranteed to have exactly x initial vertices and y terminal vertices, and we also find the extremal values for the number of edges in the resulting task-dependency graphs as a function of x, y, and the number of vertices. Furthermore, we asymptotically bound the expected number of edges in the resulting task-dependency graphs. Finally, we define a random process using only edge-addition and edge-removal, and we show that with high probability this random process generates an (x, y) task-dependency graph of order n with m edges.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections