Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization

DOI10.1007/s00453-014-9920-6zbMath1312.68095OpenAlexW2164433924MaRDI QIDQ2343085

Édouard Bonnet, Vangelis Th. Paschos, Bruno Escoffier, Emeric Tourniaire

Publication date: 4 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/13866

zbMATH Keywords

branchingparameterized complexitygreedyFPTlocal partitioning problems

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

Parameterized algorithms for graph partitioning problems ⋮ On the parameterized complexity of the Maximum Exposure Problem ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ Parameterized complexity of computing maximum minimal blocking and hitting sets ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel ⋮ Balanced Judicious Bipartition is Fixed-Parameter Tractable ⋮ Parameterized complexity of multi-node hubs ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Treewidth. Computations and approximations
• On cutting a few vertices from a graph
• Parameterized algorithms for graph partitioning problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Monadic second order logic on graphs with local cardinality constraints
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Color-coding
• Finding Dense Subgraphs of Sparse Graphs
• Minimum bisection is fixed parameter tractable

This page was built for publication: Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization