Evaluating topological ordering in directed acyclic graphs
Abstract
Directed acyclic graphs are often used to model situations and problems in real life. If we consider the topological ordering of the graph as a process of arranging the vertices in the best possible way considering the constraints caused by the direction of edges, then it makes sense to try to optimize this process by minimizing the distances between vertices in the ordering. For this purpose, we define measures based on distances between vertices in the topological ordering that allow us to construct a graph with optimal topological ordering regarding a specific measure thus minimizing the complexity of the system represented by the graph. We explore minimal and maximal values of the defined measures and comment on the topology of graphs for which maximal and minimal values are obtained. Potentially, the proved bounds could be used to benchmark existing algorithms, devise new approximation algorithms or branch and bound schemas for some scheduling problems that are usually of hard computational complexity.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.25
References
M. Albert and A. Frieze, Random graph orders, Order 6 (1989), 19–30.
S. Antunovic and D. Vukicevic, Detecting communities in directed acyclic networks using modified LPA algorithms, Proceedings of the 2nd Croatian Combinatorial Days (2019), 1–14.
J. Bang–Jensen, Digraphs: Theory, Algorithms and Applications, Springer–Verlag (2008).
A. Barak and P. Erdos, On the number of strongly independent vertices in a directed acyclic random graph, SIAM J. Matrix Anal. A. 5 (1984), 508–514.
S. Baskiyar and R. Abdel-Kader, Energy aware DAG scheduling in heterogeneous systems, Cluster Computing 13 (2010), 373–383.
L. Bertacco, L. Brunetta, and M. Fischetti, The linear ordering problem with cumulative costs, Eur. J. Oper. Res., 189 (2008), 1345–1357.
B. Bollobas and G. Brightwell, The structure of random graph orders, SIAM J. Discrete Math. 10 (1997), 318–335.
P. Brucker, B. Jurisch, and B. Sievers, A branch and bound algorithm for the job–shop scheduling problem, Discrete Appl. Math. 49 (1994), 107–127.
M. Convolbo and J. Chou, Cost–aware DAG scheduling algorithms for minimizing execution cost on cloud resources, The Journal of Supercomputing 72 (2016), 985–1012.
H. El–Rewini, H.H. Ali, and T. Lewis, Task scheduling in multiprocessing systems, Computer 28 (1995), 27–37.
C. Hanen and A. Munier, A study of the cyclic scheduling problem on parallel processors, Discrete Appl. Math. 57 (1995), 167–192.
J. §. Ide and F. Cozman, Random generation of Bayesian networks, Proceedings of the 16th Brazilian Symposium on artificial intelligence (2002), 175–186.
F.V. Jensen, Bayesian Networks and Decision Graphs, Springer, Berlin, (2001)
B. Karrer and M. Newman, Random graph model for directed acyclic networks, Phys. Rev. E. 80 (2009)
H. Ke and B. Liu, Project scheduling problem with stochastic activity duration times, Appl. Math. Comput. 168 (2005), 342–353.
O. Mengshoel, D. Wilkins, and D. Roth, Controlled generation of hard and easy Bayesian networks: Impact on maximal clique size in tree clustering, Artificial Intelligence 170 (2006), 1137–1174
B. Pittel and R. Tungol, A phase transition phenomenon in a random directed acyclic graph, Random Struct. Algorithms 18 (2001), 164–184.
A. Quilliot and D. Rebaine, Linear time algorithms to solve the linear ordering problem for oriented tree based graphs, RAIRO–Oper. Res. 50 (2016), 315–325.
H. Topcouglu, S. Hariri, and M.–Y. Wu, Task scheduling algorithms for heterogeneous processors, Proceedings Eighth Heterogeneous Computing Workshop (1999), 3–14.
T. Łuczak, First order properties of random posets, Order 8 (1991), 291–297.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.