Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs

DOI10.1007/3-540-57899-4_47zbMath1530.05183MaRDI QIDQ6143971

Kimio Kawaguchi, Koichi Wada

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

zbMATH Keywords

connected graphpartition problemedge disjointconnected subgraphinput graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (1)

Reconfiguration of connected graph partitions via recombination

Cites Work

• Unnamed Item
• Unnamed Item
• New results in graph routing
• A linear algorithm for bipartition of biconnected graphs
• On the complexity of partitioning graphs into connected subgraphs
• Fault-tolerant routings in a \(\kappa\)-connected network
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• A homology theory for spanning tress of a graph

This page was built for publication: Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs