A linear algorithm for bipartition of biconnected graphs

DOI10.1016/0020-0190(90)90189-5MaRDI QIDQ911298zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• A homology theory for spanning tress of a graph
• On the complexity of partitioning graphs into connected subgraphs

Cited in

(29)

• Partitioning powers of traceable or Hamiltonian graphs
• Algorithm Engineering for Optimal Graph Bipartization
• A plane graph representation of triconnected graphs
• Decomposing trees with large diameter
• Reconfiguration of connected graph partitions via recombination
• scientific article; zbMATH DE number 2230227 (Why is no real title available?)
• 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
• Solving the 2-rooted mini-max spanning forest problem by branch-and-bound
• On minimal arbitrarily partitionable graphs
• scientific article; zbMATH DE number 1522753 (Why is no real title available?)
• On the shape of decomposable trees
• Experimental and Efficient Algorithms
• Spanning tree congestion and computation of generalized Győri-Lovász partition
• Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
• A heuristic approach for dividing graphs into bi-connected components with a size constraint
• Efficient Constructions for the Győri-Lovász Theorem on Almost Chordal Graphs
• 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
• Max-min weight balanced connected partition
• On the parameterized complexity of 2-partitions

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)