Revisiting dynamic programming for finding optimal subtrees in trees

DOI10.1016/j.ejor.2005.11.005zbMath1111.90093OpenAlexW2083042895MaRDI QIDQ856203

Christian Blum

Publication date: 7 December 2006

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2005.11.005

zbMATH Keywords

heuristicsdynamic programmingcombinatorial optimization

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Dynamic programming (90C39)

Related Items (4)

Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems ⋮ Weighted target set selection on trees and cycles ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation

Uses Software

• K_TREE/K_SUBGRAPH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• Integer programming approaches to facilities layout models with forbidden areas
• \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• Variable neighborhood decomposition search for the edge weighted \(k\)-cardinality tree problem
• Decomposing Matrices into Blocks
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Spanning Trees—Short or Small

This page was built for publication: Revisiting dynamic programming for finding optimal subtrees in trees