An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs

DOI10.1007/978-3-642-23719-5_13zbMath1347.68283OpenAlexW2301629032MaRDI QIDQ3092224

Andreas Emil Feldmann, Peter Widmayer

Publication date: 16 September 2011

Published in: Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-23719-5_13

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

An exact algorithm for min-max hyperstructure equipartition with a connected constraint ⋮ Minimum bisection is NP-hard on unit disk graphs ⋮ Fast balanced partitioning is hard even on grids and trees ⋮ ILP-Based Local Search for Graph Partitioning ⋮ Algorithms and complexity for geodetic sets on partial grids ⋮ Balanced tree partition problems with virtual nodes ⋮ Corner cuts are close to optimal: from solid grids to polygons and back ⋮ Unnamed Item ⋮ On the parameterized complexity of computing balanced partitions in graphs ⋮ An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ An exact combinatorial algorithm for minimum graph bisection ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ Unnamed Item ⋮ Balanced partitions of trees and applications

This page was built for publication: An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs