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

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

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

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (56)

Construction independent spanning trees on locally twisted cubes in parallel ⋮ Independent spanning trees of chordal rings ⋮ Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity ⋮ Constructing edge-disjoint spanning trees in twisted cubes ⋮ A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks ⋮ Unnamed Item ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases ⋮ An algorithm to construct independent spanning trees on parity cubes ⋮ Reliable broadcasting in product networks ⋮ A comment on ``Independent spanning trees in crossed cubes ⋮ A plane graph representation of triconnected graphs ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Efficient algorithms for a mixed k-partition problem of graphs without specifying bases ⋮ Graph ear decompositions and graph embeddings ⋮ Distributed computing in asynchronous networks with byzantine edges ⋮ Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes ⋮ Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes ⋮ Spanning trees: A survey ⋮ Simple computation of \textit{st}-edge- and \textit{st}-numberings from ear decompositions ⋮ Independent spanning trees on twisted cubes ⋮ A fast parallel algorithm for constructing independent spanning trees on parity cubes ⋮ A linear-time algorithm for finding an ambitus ⋮ Construction of optimal independent spanning trees on folded hypercubes ⋮ Edge-orders ⋮ A parallel algorithm for constructing independent spanning trees in twisted cubes ⋮ The generalized 4-connectivity of hypercubes ⋮ On mixed connectivity certificates ⋮ Completely independent spanning trees in torus networks ⋮ Parallel construction of multiple independent spanning trees on highly scalable datacenter networks ⋮ On independent spanning trees ⋮ Constructing independent spanning trees for locally twisted cubes ⋮ Independent spanning trees on even networks ⋮ Independent spanning trees with small depths in iterated line digraphs ⋮ Structural properties of subdivided-line graphs ⋮ CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2) ⋮ Broadcasting secure messages via optimal independent spanning trees in folded hypercubes ⋮ Power assignment for \(k\)-connectivity in wireless ad hoc networks ⋮ Independent spanning trees on folded hyper-stars ⋮ Constructing edge-disjoint spanning trees in locally twisted cubes ⋮ The balanced connected subgraph problem ⋮ On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\) ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ Linear time algorithms for finding independent spanning trees on pyramid networks ⋮ On mixed connectivity certificates ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ Constructing Node-Independent Spanning Trees in Augmented Cubes ⋮ A multi-tree routing scheme using acyclic orientations ⋮ Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks ⋮ Independent branchings in acyclic digraphs ⋮ A LINEAR-TIME ALGORITHM TO FIND FOUR INDEPENDENT SPANNING TREES IN FOUR CONNECTED PLANAR GRAPHS ⋮ Four Edge-Independent Spanning Trees ⋮ Independent spanning trees in crossed cubes ⋮ Independent trees in graphs

This page was built for publication: Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs