Maximum Minimal Vertex Cover Parameterized by Vertex Cover
From MaRDI portal
Publication:2946427
DOI10.1007/978-3-662-48054-0_49zbMath1380.68235OpenAlexW2400752627MaRDI QIDQ2946427
Publication date: 16 September 2015
Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_49
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (5)
Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ The many facets of upper domination ⋮ Upper Domination: Complexity and Approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation ⋮ Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Fundamentals of parameterized complexity
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Improved upper bounds for vertex cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- Approximating minimum independent dominating sets in wireless networks
- On two techniques of combining branching and treewidth
- Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
- Sparsification and subexponential approximation
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- A multivariate framework for weighted FPT algorithms
- Crown reductions for the minimum weighted vertex cover problem
- Vertex Cover: Further Observations and Further Improvements
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Parameterized Approximation via Fidelity Preserving Transformations
- On the max min vertex cover Problem
- A Note on Vertex Cover in Graphs with Maximum Degree 3
- Nondeterminism within $P^ * $
- On efficient fixed-parameter algorithms for weighted vertex cover
- On Problems as Hard as CNF-SAT
- Branching and Treewidth Based Exact Algorithms
This page was built for publication: Maximum Minimal Vertex Cover Parameterized by Vertex Cover
