Improved upper bounds for vertex cover
From MaRDI portal
Publication:708228
DOI10.1016/J.TCS.2010.06.026zbMATH Open1205.05217OpenAlexW2059451253MaRDI QIDQ708228FDOQ708228
Authors: Iyad Kanj, Ge Xia, Jianer 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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- A measure \& conquer approach for the analysis of exact algorithms
- Which problems have strongly exponential complexity?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Automata, Languages and Programming
- Vertex packings: Structural properties and algorithms
- Title not available (Why is that?)
- On the existence of subexponential parameterized algorithms
- An improved fixed-parameter algorithm for vertex cover
- Nondeterminism within $P^ * $
- Graph-Theoretic Concepts in Computer Science
- On efficient fixed-parameter algorithms for weighted vertex cover
- Title not available (Why is that?)
- Algorithms for maximum independent sets
- Crown reductions for the minimum weighted vertex cover problem
- Open problems around exact algorithms
- Vertex cover: Further observations and further improvements
- Graph-Theoretic Concepts in Computer Science
- Title not available (Why is that?)
- A general method to speed up fixed-parameter-tractable algorithms
- Solving large FPT problems on coarse-grained parallel machines
- Parameterized and Exact Computation
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- Title not available (Why is that?)
- Parameterized and Exact Computation
- Parameterized and Exact Computation
- Title not available (Why is that?)
- Algorithms and Data Structures
Cited In (only showing first 100 items - show all)
- 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
- Efficient algorithms for the max \(k\)-vertex cover problem
- Solving min ones 2-SAT as fast as vertex cover
- A parameterized complexity view on collapsing \(k\)-cores
- Compactors for parameterized counting problems
- Title not available (Why is that?)
- Conflict free version of covering problems on graphs: classical and parameterized
- Solving larger maximum clique problems using parallel quantum annealing
- Improved Upper Bounds for Partial Vertex Cover
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
- Refined memorization for vertex cover
- A refined branching algorithm for the maximum satisfiability problem
- Tractability in constraint satisfaction problems: a survey
- A randomized polynomial kernelization for vertex cover with a smaller parameter
- Enumerate and Expand: New Runtime Bounds for Vertex Cover Variants
- On computing the minimum 3-path vertex cover and dissociation number of graphs
- What's next? Future directions in parameterized complexity
- Computing connected-\(k\)-subgraph cover with connectivity requirement
- A basic parameterized complexity primer
- A polynomial kernel for 3-leaf power deletion
- Vertex cover: Further observations and further improvements
- Title not available (Why is that?)
- On efficient fixed-parameter algorithms for weighted vertex cover
- Algorithms and Computation
- Proper interval vertex deletion
- Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization
- A note on the parameterized complexity of unordered maximum tree orientation
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- On families of categorial grammars of bounded value, their learnability and related complexity questions
- Slightly superexponential parameterized problems
- Parameterized pre-coloring extension and list coloring problems
- Dynamic parameterized problems
- An improved fixed-parameter algorithm for vertex cover
- A refined algorithm for maximum independent set in degree-4 graphs
- Maximum independent sets near the upper bound
- Implicit branching and parameterized partial cover problems
- A \(2k\)-kernelization algorithm for vertex cover based on crown decomposition
- Backdoors to satisfaction
- On the complexity landscape of the domination chain
- On optimal approximability results for computing the strong metric dimension
- Improved Parameterized Upper Bounds for Vertex Cover
- Improved bounds for covering complete uniform hypergraphs
- Guarantees and limits of preprocessing in constraint satisfaction and reasoning
- Lower bounds for the graph homomorphism problem
- Parameterized and exact algorithms for class domination coloring
- New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
- Confronting intractability via parameters
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- An exact algorithm for maximum independent set in degree-5 graphs
- Enumerate and Expand: Improved Algorithms for Connected Vertex Cover and Tree Cover
- Treewidth and pathwidth parameterized by the vertex cover number
- Parameterized reductions and algorithms for a graph editing problem that generalizes vertex cover
- 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}
- Backdoors to tractable answer set programming
- On the parameterized complexity of computing balanced partitions in graphs
- The many facets of upper domination
- Intuitive Algorithms and t-Vertex Cover
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Faster FPT algorithm for 5-path vertex cover
- An improved parameterized algorithm for the \(p\)-cluster vertex deletion problem
- Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics
- Local search: is brute-force avoidable?
- Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
- A parameterized algorithm for bounded-degree vertex deletion
- Efficient parallel algorithms for parameterized problems
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Backdoors for linear temporal logic
- Winner determination algorithms for graph games with matching structures
- Above guarantee parameterization for vertex cover on graphs with maximum degree 4
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Strong Backdoors for Default Logic
- Parameterized complexity dichotomy for \((r, \ell)\)-\textsc{Vertex Deletion}
- Obtaining matrices with the consecutive ones property by row deletions
- Reducing the vertex cover number via edge contractions
- Quick separation in chordal and split graphs
- Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
- Parameterized complexity of \textsc{maximum edge colorable subgraph}
- On the complexity of wafer-to-wafer integration
- On the upward book thickness problem: combinatorial and complexity results
- Polynomial kernels for vertex cover parameterized by small degree modulators
- The monotone circuit value problem with bounded genus is in NC
- Parameterized algorithms for queue layouts
- Parameterized algorithms for book embedding problems
- Parameterized complexity of vertex deletion into perfect graph classes
- On finding separators in temporal split and permutation graphs
- Maximum common induced subgraph parameterized by vertex cover
- Parameterized algorithms for linear layouts of graphs with respect to the vertex cover number
- Fixed-parameter tractability for book drawing with bounded number of crossings per edge
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Parameterized and exact algorithms for class domination coloring
- What Is Known About Vertex Cover Kernelization?
- Parameterized algorithms for book embedding problems
- Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction
Uses Software
This page was built for publication: Improved upper bounds for vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q708228)
