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

DOI10.1007/S00453-014-9920-6MaRDI QIDQ2343085zbMATH OpenOpenAlexFDO

Authors É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

branchingFPTgreedylocal partitioning problemsparameterized complexity

Mathematics Subject Classification ID

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

Recommendations

• Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
• Parameterized algorithms for (r,l)-partization
• Clustering with Local Restrictions

Cites work

• Approximation algorithms for maximization problems arising in graph partitioning
• Color-coding
• Cutting up is hard to do: the parameterised complexity of k-cut and related problems
• Finding dense subgraphs of sparse graphs
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 1342117 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Minimum bisection is fixed parameter tractable
• Monadic second order logic on graphs with local cardinality constraints
• On cutting a few vertices from a graph
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth. Computations and approximations

Cited in

(16)

• An experimental evaluation of local search heuristics for graph partitioning
• \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
• Parameterized complexity of multi-node hubs
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• On the parameterized complexity of the Maximum Exposure Problem
• Parameterized complexity of computing maximum minimal blocking and hitting sets
• Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
• Parameterized exact and approximation algorithms for maximum k-set cover and related satisfiability problems
• scientific article; zbMATH DE number 910878 (Why is no real title available?)
• Parameterized complexity of DAG partitioning
• Balanced judicious bipartition is fixed-parameter tractable
• scientific article; zbMATH DE number 7286677 (Why is no real title available?)
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• FPT approximation and subexponential algorithms for covering few or many edges
• Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs
• Fixed-parameter algorithms for cardinality-constrained graph partitioning problems on sparse graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2343085)