Labeled search trees and amortized analysis: Improved upper bounds for NP-hard problems
From MaRDI portal
Publication:818673
DOI10.1007/s00453-004-1145-7zbMath1086.68099MaRDI 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
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Maximum Minimal Vertex Cover Parameterized by Vertex Cover, 3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size, A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Improved upper bounds for vertex cover, A top-down approach to search-trees: Improved algorithmics for 3-hitting set, 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, 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
