Parameterized algorithms for graph partitioning problems

DOI10.1007/s00224-016-9706-0zbMath1378.68094arXiv1403.0099OpenAlexW296387298MaRDI QIDQ2408556

Hadas Shachnai, Meirav Zehavi

Publication date: 12 October 2017

Published in: Theory of Computing Systems, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1403.0099

zbMATH Keywords

graph partitioningparameterized algorithmrepresentative familyrandom separation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

On the parameterized complexity of the Maximum Exposure Problem ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Parameterized Complexity of Multi-Node Hubs ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Parameterized complexity of multi-node hubs ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Treewidth. Computations and approximations
• Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
• Parameterized complexity of Vertex Cover variants
• $$(k,n-k)$$ ( k , n - k ) -Max-Cut: An $${\mathcal O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel
• Representative Sets of Product Families
• Representative Families: A Unified Tradeoff-Based Approach
• Designing FPT Algorithms for Cut Problems Using Randomized Contractions
• Deterministic Algorithms for Matching and Packing Problems Based on Representative Sets
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• VLSI Physical Design: From Graph Partitioning to Timing Closure
• Finding Dense Subgraphs of Sparse Graphs
• Exact and Approximation Algorithms for Densest k-Subgraph
• Minimum bisection is fixed parameter tractable
• Improved Upper Bounds for Partial Vertex Cover
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms

This page was built for publication: Parameterized algorithms for graph partitioning problems