Improved upper bounds for vertex cover
From MaRDI portal
Publication:708228
DOI10.1016/j.tcs.2010.06.026zbMath1205.05217MaRDI QIDQ708228
Ge Xia, Iyad A. Kanj, Jian'er Chen
Publication date: 11 October 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.026
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Beyond bidimensionality: parameterized subexponential algorithms on directed graphs, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Parameterized complexity of vertex deletion into perfect graph classes, Solving min ones 2-SAT as fast as vertex cover, A note on the parameterized complexity of unordered maximum tree orientation, Local search: is brute-force avoidable?, Guarantees and limits of preprocessing in constraint satisfaction and reasoning, Confronting intractability via parameters, On the parameterized complexity of vertex cover and edge cover with connectivity constraints, Complexity of conflict-free colorings of graphs, Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem}, On the parameterized complexity of computing balanced partitions in graphs, On computing the minimum 3-path vertex cover and dissociation number of graphs, Implicit branching and parameterized partial cover problems, On families of categorial grammars of bounded value, their learnability and related complexity questions, Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, Proper interval vertex deletion, Backdoors to tractable answer set programming, Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization, Obtaining matrices with the consecutive ones property by row deletions, New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set, Maximum common induced subgraph parameterized by vertex cover, Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics, A Basic Parameterized Complexity Primer, Backdoors to Satisfaction, What’s Next? Future Directions in Parameterized Complexity, Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved fixed-parameter algorithm for vertex cover
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- Which problems have strongly exponential complexity?
- A general method to speed up fixed-parameter-tractable algorithms
- Solving large FPT problems on coarse-grained parallel machines
- On the existence of subexponential parameterized algorithms
- Crown reductions for the minimum weighted vertex cover problem
- Open problems around exact algorithms
- Vertex Cover: Further Observations and Further Improvements
- A measure & conquer approach for the analysis of exact algorithms
- Algorithms for maximum independent sets
- Vertex packings: Structural properties and algorithms
- Nondeterminism within $P^ * $
- On efficient fixed-parameter algorithms for weighted vertex cover
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Automata, Languages and Programming
- Algorithms and Data Structures
- Graph-Theoretic Concepts in Computer Science
