A linear algorithm for bipartition of biconnected graphs

DOI10.1016/0020-0190(90)90189-5zbMath0696.68074OpenAlexW1997165382MaRDI QIDQ911298

Naomi Takahashi, Takao Nishizeki, Hitoshi Suzuki

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90189-5

zbMATH Keywords

depth-first searchlinear algorithmbipartition of biconnected graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Algorithms in computer science (68W99)

Related Items (24)

A linear-time algorithm for four-partitioning four-connected planar graphs ⋮ Finding good 2-partitions of digraphs. I. Hereditary properties ⋮ Finding good 2-partitions of digraphs. II. Enumerable properties ⋮ FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX–MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS ⋮ Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases ⋮ Max-min weight balanced connected partition ⋮ Partitioning powers of traceable or Hamiltonian graphs ⋮ Degree-constrained 2-partitions of graphs ⋮ A plane graph representation of triconnected graphs ⋮ Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Efficient algorithms for a mixed k-partition problem of graphs without specifying bases ⋮ On the parameterized complexity of 2-partitions ⋮ On minimal arbitrarily partitionable graphs ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Optimal fault-tolerant routings for connected graphs ⋮ Decomposing trees with large diameter ⋮ Bisecting a 4-connected graph with three resource sets ⋮ Optical implementation of rearrangeable nonblocking double banyan interconnection network in free space ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Unnamed Item ⋮ Solving the 2-rooted mini-max spanning forest problem by branch-and-bound ⋮ On the shape of decomposable trees

Cites Work

• On the complexity of partitioning graphs into connected subgraphs
• A homology theory for spanning tress of a graph
• Unnamed Item

This page was built for publication: A linear algorithm for bipartition of biconnected graphs