Name
Abstract | ||
|---|---|---|
We call a topological ordering of a weighted directed acyclic graph non-negative if the sum of weights on the vertices in any prefix of the ordering is non-negative. We investigate two processes for constructing non-negative topological orderings of weighted directed acyclic graphs. The first process is called a mark sequence and the second is a generalization called a mark-unmark sequence. We answer a question of Erickson by showing that every non-negative topological ordering that can be realized by a mark-unmark sequence can also be realized by a mark sequence. We also investigate the question of whether a given weighted directed acyclic graph has a non-negative topological ordering. We show that even in the simple case when every vertex is a source or a sink the question is NP-complete. We introduce a graph algorithm called a mark-unmark sequence for finding topological orderings of directed acyclic graphs.We show that if a directed acyclic graph has a non-negative mark-unmark sequence, then it has non-negative mark sequence.We show that it is NP-hard to decide if a directed acyclic graph has a non-negative topological ordering. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.ipl.2016.04.007 | Inf. Process. Lett. |
Keywords | Field | DocType |
Topological ordering,Directed acyclic graph,Graph Algorithms | Acyclic dependencies principle,Discrete mathematics,Topology,Combinatorics,Path (graph theory),Topological sorting,Directed acyclic graph,Directed acyclic word graph,Feedback arc set,Mathematics,Moral graph,Topological graph | Journal |
Volume | Issue | ISSN |
116 | 9 | 0020-0190 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dániel Gerbner | 1 | 46 | 21.61 |
| Balázs Keszegh | 2 | 156 | 24.36 |
| Cory Palmer | 3 | 44 | 10.33 |
| Dömötör Pálvölgyi | 4 | 15 | 3.79 |