The bisection width of grid graphs

DOI10.1007/BF01305310zbMath0839.68076OpenAlexW3139448511MaRDI QIDQ4866677

Christos H. Papadimitriou, Martha Sideris

Publication date: 18 March 1996

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01305310

zbMATH Keywords

grid graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

Minimum bisection is NP-hard on unit disk graphs ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Brushing without capacity restrictions ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ Restricted Cuts for Bisections in Solid Grids: A Proof via Polygons

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• On the Optimal Bisection of a Polygon
• Hamilton Paths in Grid Graphs

This page was built for publication: The bisection width of grid graphs