Bisecting a 4-connected graph with three resource sets

DOI10.1016/j.dam.2007.03.004zbMath1142.05068OpenAlexW2154818280MaRDI QIDQ997070

Hiroshi Nagamochi, Kengo Iwata, Toshimasa Ishii

Publication date: 19 July 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://barrel.repo.nii.ac.jp/?action=repository_action_common_download&item_id=49&item_no=1&attribute_id=19&file_no=1

zbMATH Keywords

graph algorithmgraph bisectiongraph connectivitygraph partition

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

A deterministic annealing algorithm for approximating a solution of the min-bisection problem ⋮ A deterministic annealing algorithm for the minimum concave cost network flow problem

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• A linear algorithm for bipartition of biconnected graphs
• On the complexity of partitioning graphs into connected subgraphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Algorithms for ham-sandwich cuts
• Convex embeddings and bisections of 3-connected graphs
• A tabu search heuristic and adaptive memory procedure for political districting
• A recursive characterization of the 4-connected graphs