A linear-time algorithm for finding an ambitus

DOI10.1007/BF01758776MaRDI QIDQ1186786zbMATH OpenOpenAlexFDO

Authors S. Singh, Bhubaneswar Mishra, Robert E. Tarjan

Publication date 28 June 1992

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01758776

zbMATH Keywords

ambitusbridgescyclegraph algorithmspaths

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Review text

The paper presents a linear algorithm for finding an ambitus in a 2- connected graph \(G\). Let \(s\), \(t\) be two distinct vertices of \(G\) and \(P\), \(Q\) two internally disjoint \(s-t\) paths in \(G\). These two paths form an ambitus in \(G\) if components of \(G-(P\cup Q)\) called bridges and divided into groups \(B^ P\), \(B^ Q\), \(B^{PQ}\) satisfy the property that a bridge in one group does not interlace with any bridge in the other group. That means an ambitus is a cycle cutting the graph into disjoint pieces which can be investigated separately. Fast finding an ambitus makes it possible to employ the divide-and-conquer paradigm in designing some graph algorithms.

Recommendations

• scientific article; zbMATH DE number 519598
• Simple linear time approximation algorithm for betweenness
• A simple linear expected time algorithm for finding a Hamilton path
• A linear time and space algorithm for detecting path intersection
• A provably fast linear-expected-time maxima-finding algorithm
• Approximate solution of a linear time-optimal problem
• Finding Tutte paths in linear time
• A linear time Oslo algorithm
• Calculating a linear-time solution to the densest-segment problem

Cites work

• Bridges and Hamiltonian circuits in planar graphs
• Depth-First Search and Linear Graph Algorithms
• Dividing a Graph into Triconnected Components
• Efficient Planarity Testing
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• scientific article; zbMATH DE number 4117882 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3241107 (Why is no real title available?)
• scientific article; zbMATH DE number 3378931 (Why is no real title available?)

Cited in

(3)

• A lower bound of the expected maximum number of edge-disjoint \(s\)--\(t\) paths on probabilistic graphs
• Crossing and Weighted Crossing Number of Near-Planar Graphs
• Crossing number and weighted crossing number of near-planar graphs

This page was built for publication: A linear-time algorithm for finding an ambitus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186786)