On the parameterized complexity of vertex cover and edge cover with connectivity constraints

DOI10.1016/j.tcs.2014.10.035zbMath1315.68150OpenAlexW2036594069WikidataQ59864899 ScholiaQ59864899MaRDI QIDQ482281

Fedor V. Fomin, Geevarghese Philip, Saket Saurabh, Henning Fernau

Publication date: 22 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.035

zbMATH Keywords

edge coververtex coverparameterized complexitykernel lower boundsconnectivity problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Connectivity (05C40)

Related Items (3)

On the parameterized complexity of b-\textsc{chromatic number} ⋮ Kernels for packing and covering problems ⋮ An efficient local search framework for the minimum weighted vertex cover problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Vertex and edge covers with clustering properties: Complexity and algorithms
• On problems without polynomial kernels
• Approximation algorithms for the test cover problem
• Parameterized measure \& conquer for problems with no small kernels
• Parametrized complexity theory.
• The number of trees
• Vertex Cover: Further Observations and Further Improvements
• On Multiway Cut Parameterized above Lower Bounds
• Deterministic Parameterized Connected Vertex Cover
• New Parameterized Algorithms for the Edge Dominating Set Problem
• Paths, Flowers and Vertex Cover
• An Algorithm for a Minimum Cover of a Graph
• The Curse of Connectivity: t-Total Vertex (Edge) Cover
• Incompressibility through Colors and IDs
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Constant Time Generation of Rooted Trees
• Edge Dominating Sets in Graphs
• Fast algorithms for genegrating integer partitions
• Color-coding
• The Parametrized Complexity of Some Fundamental Problems in Coding Theory
• Reducibility among Combinatorial Problems
• On the completeness of a generalized matching problem
• Counting Subgraphs via Homomorphisms
• Parallel Processing and Applied Mathematics
• Counting Subgraphs via Homomorphisms

This page was built for publication: On the parameterized complexity of vertex cover and edge cover with connectivity constraints