Implicit branching and parameterized partial cover problems
From MaRDI portal
Publication:657922
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
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
