On the parameterized complexity of computing balanced partitions in graphs
From MaRDI portal
Publication:493645
DOI10.1007/s00224-014-9557-5zbMath1329.68150arXiv1312.7014OpenAlexW2032278054MaRDI QIDQ493645
Ondřej Suchý, René van Bevern, Andreas Emil Feldmann, Manuel Sorge
Publication date: 4 September 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1312.7014
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, Minimum Bisection Is Fixed-Parameter Tractable, The complexity of tree partitioning, The parameterized complexity of the minimum shared edges problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Fast balanced partitioning is hard even on grids and trees
- Improved upper bounds for vertex cover
- A framework for solving VLSI graph layout problems
- The treewidth and pathwidth of hypercubes
- Parameterized graph separation problems
- Balanced graph partitioning
- On the parameterized complexity of multiple-interval graph problems
- Some simplified NP-complete graph problems
- Treewidth. Computations and approximations
- Bin packing with fixed number of bins revisited
- Upper bounds to the clique width of graphs
- Parametrized complexity theory.
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- On the Parameterized Complexity of Computing Graph Bisections
- Expanding the Expressive Power of Monadic Second-Order Logic on Restricted Graph Classes
- Cluster Vertex Deletion: A Parameterization between Vertex Cover and Clique-Width
- Finding small separators in linear time via treewidth reduction
- An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
- Vertex Bisection is Hard, too
- A scalable multi-level preconditioner for matrix-free µ-finite element analysis of human bone structures
- Kernelization: New Upper and Lower Bound Techniques
- What Makes Equitable Connected Partition Easy
- Applications of a Planar Separator Theorem
- Partitioning Planar Graphs
- Kernelization Lower Bounds by Cross-Composition
- Fibonacci heaps and their uses in improved network optimization algorithms
- Exact Combinatorial Branch-and-Bound for Graph Bisection
- Minimum bisection is fixed parameter tractable
- Graph-Theoretic Concepts in Computer Science
