  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.
