Paper Info
Title
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 a 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.
Year
DOI
Venue
2021
10.5614/ejgta.2021.9.2.25
ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS
Keywords
DocType
Volume
directed acyclic graph, topological order, measure, extremal values
Journal
9
Issue
ISSN
Citations 
2
2338-2287
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Suzana Antunovic100.34
Damir Vukicevic200.68