On the parameterized complexity of computing balanced partitions in graphs

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

zbMATH Keywords

NP-hard problemsbisectioncliquewidthproblem kernelizationtreewidth reduction

Mathematics Subject Classification ID

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 (4)

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

• ParFE

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

This page was built for publication: On the parameterized complexity of computing balanced partitions in graphs