Subexponential algorithms for partial cover problems

DOI10.1016/j.ipl.2011.05.016zbMath1260.05159OpenAlexW2047916710WikidataQ60488590 ScholiaQ60488590MaRDI QIDQ1944141

Venkatesh Raman, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2009/2318/

zbMATH Keywords

graph algorithmsparameterized algorithmssubexponential algorithmspartial dominating setpartial cover problems

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

On the Parameterized Complexity of the Expected Coverage Problem ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ On the parameterized complexity of the expected coverage problem ⋮ Graph Minors and Parameterized Algorithm Design ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Parameterized complexity of perfectly matched sets ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Combing a Linkage in an Annulus ⋮ Representative families: a unified tradeoff-based approach ⋮ FPT approximation and subexponential algorithms for covering few or many edges ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Inclusion/exclusion meets measure and conquer ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ Partial vertex cover on graphs of bounded degeneracy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Linearity of grid minors in treewidth with applications through bidimensionality
• Computing small partial coverings
• Quickly excluding a planar graph
• Graph minors. XIII: The disjoint paths problem
• Parameterized complexity of Vertex Cover variants
• Parametrized complexity theory.
• Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract)
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• The Induced Disjoint Paths Problem
• An Improved Algorithm for Finding Cycles Through Elements
• Contraction Bidimensionality: The Accurate Picture
• Approximation algorithms for partial covering problems
• Improved Upper Bounds for Partial Vertex Cover
• Partial vs. Complete Domination: t-Dominating Set
• Intuitive Algorithms and t-Vertex Cover

This page was built for publication: Subexponential algorithms for partial cover problems