New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem

DOI10.1016/j.cor.2003.11.007zbMath1107.90044OpenAlexW2010597367MaRDI QIDQ1764754

Maria J. Blesa, Christian Blum

Publication date: 22 February 2005

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2003.11.007

zbMATH Keywords

Tabu searchCombinatorial optimizationMetaheuristicsSpanning treesEvolutionary computationAnt Colony Optimization\(k\)-cardinality tree problem

Mathematics Subject Classification ID

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

Related Items

Remarks on the application of genetic algorithm and tabu search method to nonlinear spanning tree problems, Revisiting dynamic programming for finding optimal subtrees in trees, Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, On the finite-time dynamics of ant colony optimization, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, NEW METAHEURISTIC APPROACHES FOR THE LEAF-CONSTRAINED MINIMUM SPANNING TREE PROBLEM, LS(graph): a constraint-based local search for constraint optimization on trees and paths, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, An ant colony optimization approach for the multidimensional knapsack problem, The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation, New branch-and-bound algorithms for k-cardinality tree problems

Uses Software

• Tabu search
• K_TREE/K_SUBGRAPH
• HC-ACO

Cites Work

• 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
• 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
• A framework for the description of evolutionary algorithms
• Local search algorithms for the \(k\)-cardinality tree problem.
• Future paths for integer programming and links to artificial intelligence
• Decomposing Matrices into Blocks
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Spanning Trees—Short or Small