Refined memorization for vertex cover

DOI10.1016/J.IPL.2004.10.003MaRDI QIDQ835007zbMATH OpenOpenAlexFDO

Authors 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 complexityvertex covermemorization

Mathematics Subject Classification ID

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

Recommendations

• Parameterized and Exact Computation
• Improved upper bounds for vertex cover
• An improved fixed-parameter algorithm for vertex cover
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities
• On efficient fixed-parameter algorithms for weighted vertex cover

Cites work

• scientific article; zbMATH DE number 3887060 (Why is no real title available?)
• scientific article; zbMATH DE number 1304341 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A general method to speed up fixed-parameter-tractable algorithms
• Algorithms for maximum independent sets
• An improved fixed-parameter algorithm for vertex cover
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Nondeterminism within $P^ * $
• On efficient fixed-parameter algorithms for weighted vertex cover
• Vertex cover: Further observations and further improvements

Cited in

(18)

• Exact algorithms and applications for tree-like Weighted Set Cover
• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Minimum Leaf Out-Branching Problems
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• Parameterized and Exact Computation
• Improved upper bounds for vertex cover
• On two techniques of combining branching and treewidth
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• A bounded search tree algorithm for parameterized face cover
• Rank vertex cover as a natural problem for algebraic compression
• Maximum minimal vertex cover parameterized by vertex cover
• On parameterized exponential time complexity
• Generating Faster Algorithms for d-Path Vertex Cover
• Deterministic algorithms for matching and packing problems based on representative sets
• Maximum minimal vertex cover parameterized by vertex cover
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• An exact exponential time algorithm for \textsc{Power} \textsc{Dominating} \textsc{Set}
• A multivariate framework for weighted FPT algorithms

This page was built for publication: Refined memorization for vertex cover

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q835007)