Eager st-Ordering


Dateien zu dieser Ressource

Prüfsumme: MD5:96ff3f0db464ee1f58f9aa4acc80876b

BRANDES, Ulrik, 2002. Eager st-Ordering

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

Brandes, Ulrik application/pdf 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 deposit-license

Dateiabrufe seit 01.10.2014 (Informationen über die Zugriffsstatistik)

preprint_171.pdf 69

Das Dokument erscheint in:

KOPS Suche


Mein Benutzerkonto