Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs

DOI10.1016/0196-6774(88)90015-6zbMath0672.05056MaRDI QIDQ3825103

Joseph Cheriyan, S. N. Maheshwari

Publication date: 1988

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(88)90015-6

zbMATH Keywords

3-connected graph; ear decomposition; spanning trees; nonseparating induced cycle

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

90B10: Deterministic network models in operations research

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2), Independent spanning trees with small depths in iterated line digraphs, Constructing edge-disjoint spanning trees in locally twisted cubes, On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\), Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases, A linear-time algorithm for finding an ambitus, On independent spanning trees, On mixed connectivity certificates, Independent branchings in acyclic digraphs, Independent trees in graphs, Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity, Reliable broadcasting in product networks, A multi-tree routing scheme using acyclic orientations, Power assignment for \(k\)-connectivity in wireless ad hoc networks