The bisection width of grid graphs
From MaRDI portal
Recommendations
- An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids
- Restricted cuts for bisections in solid grids: a proof via polygons
- Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
Cites work
Cited in
(13)- Bisection width of transposition graphs
- Corner cuts are close to optimal: from solid grids to polygons and back
- A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
- An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Minimum bisection is NP-hard on unit disk graphs
- Brushing without capacity restrictions
- An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
- Restricted cuts for bisections in solid grids: a proof via polygons
- Algorithms for the minimum non-separating path and the balanced connected bipartition problems on grid graphs
- Fast balanced partitioning is hard even on grids and trees
- On the bisection width of the transposition network
- The Rank-Width of the Square Grid
- Girth, Pebbling, and Grid Thresholds
This page was built for publication: The bisection width of grid graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4866677)
