Schlipf, LenaLenaSchlipfSchmidt, Jens M.Jens M.Schmidt2020-10-192020-10-192019-05-01Information Processing Letters (2019)http://hdl.handle.net/11420/7604We 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.en0020-019020195863Ear decompositionsGraph algorithmsLinear timest-Edge-numberingsst-NumberingsJournal Article10.1016/j.ipl.2019.01.008Other