A linear algorithm for bipartition of biconnected graphs

DOI10.1016/0020-0190(90)90189-5zbMATH Open0696.68074OpenAlexW1997165382MaRDI QIDQ911298FDOQ911298

Authors: Hitoshi Suzuki, Naomi Takahashi, Takao Nishizeki 

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

Recommendations

• scientific article; zbMATH DE number 1262808
• An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
• A linear time algorithm for graph partition problems
• scientific article; zbMATH DE number 409492
• A robust algorithm for bisecting a triconnected graph with two resource sets

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)

Cites Work

• On the complexity of partitioning graphs into connected subgraphs
• Title not available (Why is that?)
• A homology theory for spanning tress of a graph

Cited In (29)

• Partitioning powers of traceable or Hamiltonian graphs
• Algorithm Engineering for Optimal Graph Bipartization
• A plane graph representation of triconnected graphs
• Reconfiguration of connected graph partitions via recombination
• Decomposing trees with large diameter
• Title not available (Why is that?)
• A linear-time algorithm for four-partitioning four-connected planar graphs
• Finding good 2-partitions of digraphs. I. Hereditary properties
• Bisecting a 4-connected graph with three resource sets
• Degree-constrained 2-partitions of graphs
• Efficient algorithms for a mixed \(k\)-partition problem of graphs without specifying bases
• Efficient algorithms for a mixed k-partition problem of graphs without specifying bases
• Optimal fault-tolerant routings for connected graphs
• Fully polynomial-time approximation schemes for the max-min connected partition problem on interval graphs
• Experimental and Efficient Algorithms
• Title not available (Why is that?)
• Solving the 2-rooted mini-max spanning forest problem by branch-and-bound
• On minimal arbitrarily partitionable graphs
• On the shape of decomposable trees
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• Reconfiguration of connected graph partitions via recombination
• Optical implementation of rearrangeable nonblocking double banyan interconnection network in free space
• Finding good 2-partitions of digraphs. II. Enumerable properties
• Balanced connected partitions of graphs: approximation, parameterization and lower bounds
• On the parameterized complexity of 2-partitions
• Max-min weight balanced connected partition

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

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