Refined memorization for vertex cover

DOI10.1016/J.IPL.2004.10.003zbMATH Open1173.68529OpenAlexW1976697697MaRDI QIDQ835007FDOQ835007

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

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

zbMATH Keywords

computational complexityvertex covermemorization

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• An improved fixed-parameter algorithm for vertex cover
• Nondeterminism within $P^ * $
• On efficient fixed-parameter algorithms for weighted vertex cover
• Algorithms for maximum independent sets
• Vertex cover: Further observations and further improvements
• Title not available (Why is that?)
• A general method to speed up fixed-parameter-tractable algorithms

Cited In (18)

• A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
• Minimum Leaf Out-Branching Problems
• Parameterized and Exact Computation
• Enumerate and expand: Improved algorithms for connected vertex cover and tree cover
• 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
• Exact algorithms and applications for tree-like Weighted Set Cover

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)