Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
DOI10.1007/S00453-004-1145-7zbMATH Open1086.68099OpenAlexW2106457067MaRDI QIDQ818673FDOQ818673
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
Recommendations
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)
Cited In (19)
- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- 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
- Algorithms and Computation
- Improved upper bounds for vertex cover
- 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
- Maximum Weighted Independent Set: Effective Reductions and Fast Algorithms on Sparse Graphs
- Fast algorithms for max independent set
- Generating Faster Algorithms for d-Path Vertex Cover
- Improved algorithms for the general exact satisfiability problem
- Maximum minimal vertex cover parameterized by vertex cover
- Parameterized measure \& conquer for problems with no small kernels
- A multivariate framework for weighted FPT algorithms
- Further improvements for SAT in terms of formula length
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)
