Topological orderings of weighted directed acyclic graphs

DOI10.1016/J.IPL.2016.04.007zbMATH Open1358.05132arXiv1310.0516OpenAlexW1831311575MaRDI QIDQ284347FDOQ284347

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the complexity and approximation of syntenic distance

Cited In (6)

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

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)