Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems

DOI10.1007/S00453-004-1145-7MaRDI QIDQ818673zbMATHOpenAlexFDO

Authors Iyad Kanj, Ge Xia, Jianer Chen

Publication date 21 March 2006

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-004-1145-7

zbMATH Keywords

vertex covermaximum independent set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Algorithms and Computation
• A note on vertex cover in graphs with maximum degree 3
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• Improved upper bounds for vertex cover
• scientific article; zbMATH DE number 1508265

Cited in

(19)

• Parameterized measure \& conquer for problems with no small kernels
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Fixed-parameter approximation: conceptual framework and approximability results
• Generating Faster Algorithms for d-Path Vertex Cover
• Improved upper bounds for vertex cover
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
• Improved algorithms for the general exact satisfiability problem
• Further improvements for SAT in terms of formula length
• Above guarantee parameterization for vertex cover on graphs with maximum degree 4
• Fast algorithms for max independent set
• A multivariate framework for weighted FPT algorithms
• Enumerate and measure: improving parameter budget management
• Maximum minimal vertex cover parameterized by vertex cover
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• Algorithms and Computation
• Faster computation of maximum independent set and parameterized vertex cover for graphs with maximum degree 3
• 3-hitting set on bounded degree hypergraphs: upper and lower bounds on the kernel size
• Maximum minimal vertex cover parameterized by vertex cover

This page was built for publication: Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q818673)