Eager st-Ordering

Cite This

Files in this item

Checksum: MD5:96ff3f0db464ee1f58f9aa4acc80876b

BRANDES, Ulrik, 2002. Eager st-Ordering

@unpublished{Brandes2002Eager-6264, title={Eager st-Ordering}, year={2002}, author={Brandes, Ulrik} }

Brandes, Ulrik application/pdf terms-of-use Given a biconnected graph G=(V, E) and an edge {s,t} in E, an st-ordering is an ordering v1,...,vn of V such that s=v1, t=vn, and every other vertex has both a higher-numbered and a lower-numbered neighbor. Previous linear-time algorithms to compute such orderings are based on a preprocessing step in which depth-first search is used to compute lowpoints. The actual ordering is determined only in a second pass over the graph.<br /><br />We present a new, incremental algorithm that does not require lowpoint information and, throughout a single depth-first traversal, maintains an st-ordering of the biconnected component of {s,t} in the traversed subgraph. 2002 Brandes, Ulrik Eager st-Ordering 2011-03-24T16:10:36Z 2011-03-24T16:10:36Z eng

Downloads since Oct 1, 2014 (Information about access statistics)

preprint_171.pdf 144

This item appears in the following Collection(s)

Search KOPS


My Account