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

DOI10.1007/S00453-004-1145-7MaRDI QIDQ818673zbMATH OpenOpenAlexFDO

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)

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

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)