Implicit branching and parameterized partial cover problems

DOI10.1016/j.jcss.2010.12.002zbMath1245.05124OpenAlexW2021156120WikidataQ60488569 ScholiaQ60488569MaRDI QIDQ657922

Saket Saurabh, Omid Amini, Fedor V. Fomin

Publication date: 11 January 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.12.002

zbMATH Keywords

implicit branchingpartial covering problems in graphs

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs, (Total) vector domination for graphs with bounded branchwidth, Subexponential Fixed-Parameter Algorithms for Partial Vector Domination, Bivariate Complexity Analysis of Almost Forest Deletion, On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems, On the partial vertex cover problem in bipartite graphs -- a parameterized perspective, FPT approximation and subexponential algorithms for covering few or many edges, Subexponential fixed-parameter algorithms for partial vector domination, Inclusion/exclusion meets measure and conquer, The complexity of mixed-connectivity, Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs, Partial vertex cover on graphs of bounded degeneracy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Improved upper bounds for vertex cover
• Treewidth lower bounds with brambles
• Computing small partial coverings
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Graph minors. V. Excluding a planar graph
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• Local tree-width, excluded minors, and approximation algorithms
• A refined search tree technique for dominating set on planar graphs
• Using Homogeneous Weights for Approximating the Partial Cover Problem
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Polynomial-time data reduction for dominating set
• Approximation algorithms for partial covering problems
• (Meta) Kernelization
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Bidimensionality and Geometric Graphs
• Partial vs. Complete Domination: t-Dominating Set
• Intuitive Algorithms and t-Vertex Cover