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)
- 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
- Maximum minimal vertex cover parameterized by vertex cover
- Extended formulations for vertex cover
- An improved algorithm for the \((n, 3)\)-MaxSAT problem: asking branchings to satisfy the clauses
- Parameterized analysis and crossing minimization problems
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Approximation for vertex cover in \(\beta\)-conflict graphs
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Parameterized approximation via fidelity preserving transformations
- On the \(d\)-claw vertex deletion problem
- A multivariate approach for weighted FPT algorithms
- Faster exact algorithms for some terminal set problems
- Why is maximum clique often easy in practice?
- On the parameterized parallel complexity and the vertex cover problem
- Solving vertex cover in polynomial time on hyperbolic random graphs
- Maximum minimal vertex cover parameterized by vertex cover
- Parameterized complexity of maximum edge colorable subgraph
- Worst-case analysis of clique MIPs
- Title not available (Why is that?)
- The graph motif problem parameterized by the structure of the input graph
- Resolving conflicts for lower-bounded clustering
- A multivariate framework for weighted FPT algorithms
- Parameterized Algorithms for Queue Layouts
- An improved deterministic parameterized algorithm for cactus vertex deletion
- Multivariate algorithmics for finding cohesive subnetworks
- Title not available (Why is that?)
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- An articulation point-based approximation algorithm for minimum vertex cover problem
- On kernels for \(d\)-path vertex cover
- Parameterized algorithms for fixed-order book drawing with few crossings per edge
- Vertex-bipartition: a unified approach for kernelization of graph linear layout problems parameterized by vertex cover
- Parameterized and Exact Computation
- Structural parameterization of alliance problems
- Winner determination algorithms for graph games with matching structures
- Search-space reduction via essential vertices
- Rank vertex cover as a natural problem for algebraic compression
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- \(b\)-coloring parameterized by clique-width
- Fixed-parameter algorithms for computing RAC drawings of graphs
- Parameterized complexity of simultaneous planarity
- The parametrized complexity of the segment number
- Approximation algorithm and FPT algorithm for connected-\(k\)-subgraph cover on minor-free graphs
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- On the complexity of the storyplan problem
- Your rugby mates don't need to know your colleagues: triadic closure with edge colors
- 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
- Parameterized complexity of weighted target set selection
- The parameterized complexity of maximum betweenness centrality
- Fixed-parameter algorithms for computing bend-restricted RAC drawings of graphs
- An algorithmic framework for locally constrained homomorphisms
- Parameterizing path partitions
- Exploring the gap between treedepth and vertex cover through vertex integrity
- Generating Faster Algorithms for d-Path Vertex Cover
- Parameterized Complexity of Broadcasting in Graphs
- Title not available (Why is that?)
- On the \(d\)-claw vertex deletion problem
- On the upward book thickness problem: combinatorial and complexity results
- Parameterized approximation algorithms for weighted vertex cover
- Parameterized algorithms for minimum sum vertex cover
- On the parameterized complexity of non-hereditary relaxations of clique
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- 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
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)
