Refined memorization for vertex cover

DOI10.1016/j.ipl.2004.10.003zbMath1173.68529MaRDI QIDQ835007

L. Sunil Chandran, Fabrizio Grandoni

Publication date: 27 August 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2004.10.003

zbMATH Keywords

computational complexity; vertex cover; memorization

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

A novel parameterised approximation algorithm for \textsc{minimum vertex cover}, Improved upper bounds for vertex cover, Exact algorithms and applications for tree-like Weighted Set Cover, Enumerate and expand: Improved algorithms for connected vertex cover and tree cover, A bounded search tree algorithm for parameterized face cover, On two techniques of combining branching and treewidth, On parameterized exponential time complexity, Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}, An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}, Minimum Leaf Out-Branching Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved fixed-parameter algorithm for vertex cover
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• A general method to speed up fixed-parameter-tractable algorithms
• Vertex Cover: Further Observations and Further Improvements
• Algorithms for maximum independent sets
• Nondeterminism within $P^ * $
• On efficient fixed-parameter algorithms for weighted vertex cover