TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. TUHH
  3. Publication References
  4. Simple computation of st-edge- and st-numberings from ear decompositions
 
Options

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

Publikationstyp
Journal Article
Date Issued
2019-05-01
Sprache
English
Author(s)
Schlipf, Lena  
Schmidt, Jens M.  orcid-logo
TORE-URI
http://hdl.handle.net/11420/7604
Journal
Information processing letters  
Volume
145
Start Page
58
End Page
63
Citation
Information Processing Letters (2019)
Publisher DOI
10.1016/j.ipl.2019.01.008
Scopus ID
2-s2.0-85060708387
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
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback