An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs

DOI10.1007/s00453-014-9928-yzbMath1307.05211OpenAlexW2109595435MaRDI QIDQ2258080

Andreas Emil Feldmann, Peter Widmayer

Publication date: 2 March 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-014-9928-y

zbMATH Keywords

planar graphsbisectionsolid grid graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ The complexity of tree partitioning

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• Parallel approximation schemes for problems on planar graphs
• Corner cuts are close to optimal: from solid grids to polygons and back
• On the Parameterized Complexity of Computing Graph Bisections
• Minimum Bisection Is NP-hard on Unit Disk Graphs
• An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
• Edge Separators of Planar and Outerplanar Graphs With Applications
• The bisection width of grid graphs
• Finding minimum-quotient cuts in planar graphs
• Minimum bisection is fixed parameter tractable
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique

This page was built for publication: An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs