Bisecting a 4-connected graph with three resource sets

DOI10.1016/J.DAM.2007.03.004MaRDI QIDQ997070zbMATH OpenOpenAlexFDO

Authors Toshimasa Ishii, Kengo Iwata, Hiroshi Nagamochi

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 partitiongraph algorithmgraph connectivitygraph bisection

Mathematics Subject Classification ID

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

Recommendations

• Algorithms and Computation
• scientific article; zbMATH DE number 1522947
• 2-bisections in claw-free cubic multigraphs
• A robust algorithm for bisecting a triconnected graph with two resource sets
• Convex embeddings and bisections of 3-connected graphs

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3688765 (Why is no real title available?)
• A linear algorithm for bipartition of biconnected graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A recursive characterization of the 4-connected graphs
• A tabu search heuristic and adaptive memory procedure for political districting
• Algorithms for ham-sandwich cuts
• Approximating the Maximally Balanced Connected Partition Problem in graphs
• Convex embeddings and bisections of 3-connected graphs
• On the complexity of partitioning graphs into connected subgraphs

Cited in

(6)

• A deterministic annealing algorithm for approximating a solution of the min-bisection problem
• Convex embeddings and bisections of 3-connected graphs
• scientific article; zbMATH DE number 1522947 (Why is no real title available?)
• A robust algorithm for bisecting a triconnected graph with two resource sets
• A deterministic annealing algorithm for the minimum concave cost network flow problem
• Algorithms and Computation

This page was built for publication: Bisecting a 4-connected graph with three resource sets

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