Implicit branching and parameterized partial cover problems
From MaRDI portal
Publication:657922
DOI10.1016/J.JCSS.2010.12.002zbMATH Open1245.05124OpenAlexW2021156120WikidataQ60488569 ScholiaQ60488569MaRDI QIDQ657922FDOQ657922
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
Recommendations
- Implicit branching and parameterized partial cover problems (extended abstract)
- Algorithmic aspects of branched coverings
- Subexponential algorithms for partial cover problems
- Subexponential algorithms for partial cover problems
- A unified approach to approximating partial covering problems
- A Unified Approach to Approximating Partial Covering Problems
- Approximation algorithms for partial covering problems
- The approximability of partial vertex covers in trees
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- On the parameterized complexity of the expected coverage problem
Cites Work
- Computing small partial coverings
- Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
- Call routing and the ratcatcher
- Parameterized complexity of Vertex Cover variants
- Parametrized complexity theory.
- Using homogeneous weights for approximating the partial cover problem
- Algorithms for facility location problems with outliers. (Extended abstract)
- Approximation algorithms for partial covering problems
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Quickly excluding a planar graph
- Title not available (Why is that?)
- (Meta) Kernelization
- Bidimensionality and Geometric Graphs
- Improved upper bounds for vertex cover
- Partial vs. Complete Domination: t-Dominating Set
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Polynomial-time data reduction for dominating set
- Diameter and treewidth in minor-closed graph families
- Subexponential parameterized algorithms
- Graph minors. XVI: Excluding a non-planar graph
- Local tree-width, excluded minors, and approximation algorithms
- Diameter and treewidth in minor-closed graph families, revisited
- A refined search tree technique for dominating set on planar graphs
- Treewidth lower bounds with brambles
- Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
- Intuitive Algorithms and t-Vertex Cover
Cited In (15)
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
- Subexponential fixed-parameter algorithms for partial vector domination
- (Total) vector domination for graphs with bounded branchwidth
- FPT approximation and subexponential algorithms for covering few or many edges
- Bivariate Complexity Analysis of Almost Forest Deletion
- Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- The complexity of mixed-connectivity
- Subexponential Fixed-Parameter Algorithms for Partial Vector Domination
- Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
- Inclusion/exclusion meets measure and conquer
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- Partial vertex cover on graphs of bounded degeneracy
This page was built for publication: Implicit branching and parameterized partial cover problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657922)
