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

DOI10.1007/s00453-004-1145-7zbMath1086.68099OpenAlexW2106457067MaRDI QIDQ818673

Ge Xia, Iyad A. Kanj, Jian'er 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

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

Related Items (16)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Fixed-parameter approximation: conceptual framework and approximability results ⋮ A top-down approach to search-trees: Improved algorithmics for 3-hitting set ⋮ A multivariate framework for weighted FPT algorithms ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ A novel parameterised approximation algorithm for \textsc{minimum vertex cover} ⋮ Further improvements for SAT in terms of formula length ⋮ Fast algorithms for max independent set ⋮ Improved algorithms for the general exact satisfiability problem ⋮ Parameterized measure \& conquer for problems with no small kernels ⋮ Improved upper bounds for vertex cover ⋮ Enumerate and Measure: Improving Parameter Budget Management ⋮ 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 ⋮ Above guarantee parameterization for vertex cover on graphs with maximum degree 4

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