Fast balanced partitioning is hard even on grids and trees
From MaRDI portal
Publication:388790
DOI10.1016/j.tcs.2013.03.014zbMath1292.68165arXiv1111.6745OpenAlexW2005606079MaRDI QIDQ388790
Publication date: 7 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1111.6745
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
On the parameterized complexity of computing balanced partitions in graphs ⋮ Parameterized complexity of asynchronous border minimization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A framework for solving VLSI graph layout problems
- Balanced graph partitioning
- Some simplified NP-complete graph problems
- Highly connected sets and the excluded grid theorem
- Parallel approximation schemes for problems on planar graphs
- Fast Balanced Partitioning Is Hard Even on Grids and Trees
- 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
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
- Applications of a Planar Separator Theorem
- Edge Separators of Planar and Outerplanar Graphs With Applications
- Fast Approximate Graph Partitioning Algorithms
- How Good is Recursive Bisection?
- The bisection width of grid graphs
- Excluded minors, network decomposition, and multicommodity flow
- Finding minimum-quotient cuts in planar graphs
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Expander flows, geometric embeddings and graph partitioning
