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)
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 ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ Dynamic parameterized problems ⋮ The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification ⋮ Exploiting dominance conditions for computing non trivial worst-case complexity for bounded combinatorial optimization problems ⋮ Computing small partial coverings ⋮ On the Power of Simple Reductions for the Maximum Independent Set Problem ⋮ On two techniques of combining branching and treewidth ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3 ⋮ Algorithms for optimal outlier removal ⋮ FPT is characterized by useful obstruction sets ⋮ On parameterized exponential time complexity ⋮ An improved kernel size for rotation distance in binary trees ⋮ An improved kernelization algorithm for \(r\)-set packing ⋮ Revisiting connected vertex cover: FPT algorithms and lossy kernels ⋮ Multivariate analysis of orthogonal range searching and graph distances ⋮ Tight lower bounds for certain parameterized NP-hard problems ⋮ Finding, hitting and packing cycles in subexponential time on unit disk graphs ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ A refined search tree technique for dominating set on planar graphs ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Parameterized counting problems ⋮ Extending the MAX algorithm for maximum independent set ⋮ Moderately exponential time and fixed parameter approximation algorithms ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4 ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem
This page was built for publication: Vertex Cover: Further Observations and Further Improvements
