Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions

DOI10.1016/j.ipl.2019.01.008zbMath1451.05232OpenAlexW2912245476WikidataQ61772238 ScholiaQ61772238MaRDI QIDQ1730030

Lena Schlipf, Jens M. Schmidt

Publication date: 11 March 2019

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2019.01.008

zbMATH Keywords

graph algorithmslinear timeear decompositions\textit{st}-edge-numberings\textit{st}-numberings

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05)

Related Items (1)

Good acyclic orientations of 4‐regular 4‐connected graphs

Cites Work

• Algorithms for computing a parameterized \(st\)-orientation
• Maintaining order in a generalized linked list
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• st-ordering the vertices of biconnected graphs
• Computing an st-numbering
• Output-sensitive reporting of disjoint paths
• A simple test on 2-vertex- and 2-edge-connectivity
• Mondshein Sequences (a.k.a. (2,1)-Orders)
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions