Vertex Cover: Further Observations and Further Improvements
From MaRDI portal
Publication:2775891
DOI10.1006/jagm.2001.1186zbMath1017.68087OpenAlexW2026771935MaRDI QIDQ2775891
Iyad A. Kanj, Wei-Jia Jia, Jian'er Chen
Publication date: 8 July 2002
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/213321cff040cfd1ec75aded01700516a71c693b
Related Items (only showing first 100 items - show all)
A Retrospective on (Meta) Kernelization ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A Multivariate Approach for Weighted FPT Algorithms ⋮ An Improved SAT Algorithm in Terms of Formula Length ⋮ Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms ⋮ Improved MaxSAT Algorithms for Instances of Degree 3 ⋮ A Measure and Conquer Approach for the Parameterized Bounded Degree-One Vertex Deletion ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Solving larger maximum clique problems using parallel quantum annealing ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Space limited graph algorithms on big data ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Space limited linear-time graph algorithms on big data ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ FPT Algorithms for FVS Parameterized by Split and Cluster Vertex Deletion Sets and Other Parameters ⋮ Why Is Maximum Clique Often Easy in Practice? ⋮ Exploiting c-Closure in Kernelization Algorithms for Graph Problems ⋮ A Problem Kernelization for Graph Packing ⋮ Bidimensionality and Kernels ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ ON RECTANGULAR COVERING PROBLEMS ⋮ Unnamed Item ⋮ 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size ⋮ Parameterized enumeration, transversals, and imperfect phylogeny reconstruction ⋮ Linear kernels for separating a graph into components of bounded size ⋮ On the existence of subexponential parameterized algorithms ⋮ Graph separators: A parameterized view ⋮ Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms ⋮ Improved exact algorithms for MAX-SAT ⋮ Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ Safe Approximation and Its Relation to Kernelization ⋮ Refined memorization for vertex cover ⋮ A \((3+\epsilon)k\)-vertex kernel for edge-disjoint triangle packing ⋮ Equivalent characterizations of some graph problems by covering-based rough sets ⋮ Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes ⋮ A Randomized Polynomial Kernelization for Vertex Cover with a Smaller Parameter ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Constraint Satisfaction Problems Parameterized above or below Tight Bounds: A Survey ⋮ Backdoors to Satisfaction ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ Genus characterizes the complexity of certain graph problems: Some tight results ⋮ Strong computational lower bounds via parameterized complexity ⋮ A fixed-parameter tractable algorithm for matrix domination ⋮ On a generalization of Nemhauser and Trotter's local optimization theorem ⋮ A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ On product covering in 3-tier supply chain models: natural complete problems for W[3 and W[4]] ⋮ A multivariate framework for weighted FPT algorithms ⋮ Parameterized analysis and crossing minimization problems ⋮ Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter ⋮ An efficient fixed-parameter algorithm for 3-hitting set ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Separator-based data reduction for signed graph balancing ⋮ \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Improved parameterized and exact algorithms for cut problems on trees ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Kernelization and parameterized algorithms for covering a tree by a set of stars or paths ⋮ Resolution and linear CNF formulas: improved \((n,3)\)-\textsc{MaxSAT} algorithms ⋮ A kernel of order \(2k-c\log k\) for vertex cover ⋮ Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Towards optimal kernel for connected vertex cover in planar graphs ⋮ Exact algorithms for maximum weighted independent set on sparse graphs (extended abstract) ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ Nearly exact mining of frequent trees in large networks ⋮ Struction revisited ⋮ Stability preserving transformations of graphs ⋮ Lower bounds on kernelization ⋮ Confronting intractability via parameters ⋮ Enumerate and expand: Improved algorithms for connected vertex cover and tree cover ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ Properties of vertex cover obstructions ⋮ On the parameterized complexity of vertex cover and edge cover with connectivity constraints ⋮ A note on the complexity of minimum dominating set ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Solving \#SAT using vertex covers ⋮ Dealing with 4-variables by resolution: an improved MaxSAT algorithm ⋮ Crown reductions for the minimum weighted vertex cover problem ⋮ A kernel of order \(2k - c\) for Vertex Cover ⋮ Parameterized algorithms for \(d\)-hitting set: the weighted case ⋮ A linear kernel for a planar connected dominating set ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs ⋮ On the planarization of wireless sensor networks ⋮ A problem reduction based approach to discrete optimization algorithm design ⋮ Exact algorithms for maximum independent set ⋮ Improved upper bounds for vertex cover ⋮ Kernelization hardness of connectivity problems in \(d\)-degenerate graphs ⋮ On the computational hardness based on linear fpt-reductions ⋮ Fixed-parameter tractability results for full-degree spanning tree and its dual ⋮ Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
This page was built for publication: Vertex Cover: Further Observations and Further Improvements
