Topological orderings of weighted directed acyclic graphs

DOI10.1016/J.IPL.2016.04.007MaRDI QIDQ284347zbMATHOpenAlexFDO

Authors Dániel Gerbner, Balázs Keszegh, Cory Palmer, Dömötör Pálvölgyi

Publication date 18 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0516

zbMATH Keywords

directed acyclic graphgraph algorithmstopological ordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Signed and weighted graphs (05C22) Paths and cycles (05C38)

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.

Recommendations

• Evaluating topological ordering in directed acyclic graphs
• On computing the number of topological orderings of a directed acyclic graph
• On the complexity of a linear ordering of weighted directed acyclic graphs
• scientific article; zbMATH DE number 27961
• Counting acyclic orderings in directed acyclic graphs
• An Efficient Method for Indexing All Topological Orders of a Directed Graph
• On ordered graphs and graph orderings
• Topological additive numbering of directed acyclic graphs
• Ordering graphs with large eccentricity-based topological indices
• A dynamic topological sort algorithm for directed acyclic graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the complexity and approximation of syntenic distance

Cited in

(6)

• Static Scheduling with Load Balancing for Solving Triangular Band Linear Systems on Multicore Processors
• Optimizing consolidation processes in hubs: the hub-arrival-departure problem
• On the complexity of a linear ordering of weighted directed acyclic graphs
• Chain graph models: topological sorting of meta-arrows and efficient construction of \(\mathcal B\)-essential graphs
• Topological additive numbering of directed acyclic graphs
• An Efficient Method for Indexing All Topological Orders of a Directed Graph

This page was built for publication: Topological orderings of weighted directed acyclic graphs

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