Veröffentlichung

Titel:

Simple computation of st-edge- and st-numberings from ear decompositions

AutorInnen:

Lena Schlipf
Jens M. Schmidt

Kategorie:

Artikel in Zeitschriften

erschienen in:

Information Processing Letters, Vol. 145, 2019, pp. 58-63

Auflage:

Simple computation of st-edge- and st-numberings from ear decompositions

Abstract:

We propose simple algorithms for computing st-numberings and st-edge-numberings of graphs with running time O(m). Unlike previous serial algorithms, these are not dependent on an initially chosen DFS-tree. Instead, we compute st-(edge-)numberings that are consistent with any open ear decomposition D of a graph in the sense that every ear of D is numbered increasingly or decreasingly.

Recent applications need such st-numberings, and the only two linear-time algorithms that are known for this task use a complicated order data structure as black box. We avoid using this data structure by introducing a new and light-weight numbering scheme. In addition, we greatly simplify the recent algorithms for computing (the much less known) st-edge-numberings.

BibTeX-Eintrag:

@article{, author = {Lena Schlipf and Jens. M. Schmidt}, title = {Simple computation of st-edge- and st-numberings from ear decompositions}, journal = {Information Processing Letters}, volume={145}, year = {2019}, pages={58--63}, doi = {https://doi.org/10.1016/j.ipl.2019.01.008} }