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

maximum independent setvertex cover

Mathematics Subject Classification ID

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) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

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)

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

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)