Topological orderings of weighted directed acyclic graphs

Dániel Gerbner, Balázs Keszegh, Cory Palmer +1

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…