Topological orderings of weighted directed acyclic graphs

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

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Pages (from-to)564-568
Number of pages5
JournalInformation Processing Letters
Volume116
Issue number9
DOIs
StatePublished - Sep 1 2016

Keywords

  • Directed acyclic graph
  • Graph Algorithms
  • Topological ordering

Fingerprint

Dive into the research topics of 'Topological orderings of weighted directed acyclic graphs'. Together they form a unique fingerprint.

Cite this