Random processes for generating task-dependency graphs

arXiv2305.05205MaRDI QIDQ6435871FDOQ6435871

Authors: Jesse Geneson, S. F. Tsai 

Publication date: 9 May 2023

Abstract: 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.

Has companion code repository: https://github.com/jgeneson/tdgraphs

This page was built for publication: Random processes for generating task-dependency graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435871)