Options
Simple computation of st-edge- and st-numberings from ear decompositions
Publikationstyp
Journal Article
Date Issued
2019-05-01
Sprache
English
Author(s)
TORE-URI
Journal
Volume
145
Start Page
58
End Page
63
Citation
Information Processing Letters (2019)
Publisher DOI
Scopus ID
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.
Subjects
Ear decompositions
Graph algorithms
Linear time
st-Edge-numberings
st-Numberings