Local search algorithms for the \(k\)-cardinality tree problem.

DOI10.1016/S0166-218X(02)00548-6zbMath1038.90085OpenAlexW2017765977MaRDI QIDQ1811129

Christian Blum, Matthias Ehrgott

Publication date: 10 June 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00548-6

zbMATH Keywords

Genetic algorithmTabu searchCombinatorial optimizationLocal search\(k\)-cardinality tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A mixed integer linear programming model and variable neighborhood search for maximally balanced connected partition problem ⋮ Variable neighborhood decomposition search for the edge weighted \(k\)-cardinality tree problem ⋮ Revisiting dynamic programming for finding optimal subtrees in trees ⋮ Integer Programming Formulations for the k-Cardinality Tree Problem ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ Local and variable neighborhood search for the \(k\) -cardinality subgraph problem ⋮ New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation ⋮ Local search algorithms for the \(k\)-cardinality tree problem. ⋮ Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem

Uses Software

• K_TREE/K_SUBGRAPH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Faster geometric \(k\)-point MST approximation
• A framework for the description of evolutionary algorithms
• The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
• Solution of the cumulative assignment problem with a well-structured tabu search method
• Local search algorithms for the \(k\)-cardinality tree problem.
• Metaheuristics: A bibliography
• Tabu Search—Part I
• Tabu Search—Part II
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints
• Spanning Trees—Short or Small