The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation

DOI10.1016/j.dam.2009.01.017zbMath1231.05139OpenAlexW2045428711MaRDI QIDQ987675

J. Martínez

Publication date: 13 August 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.01.017

zbMATH Keywords

integer programmingLagrangian relaxation\(k\)-Cardinality tree problem

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Integer programming (90C10) Linear programming (90C05)

Related Items (6)

Computational approaches for zero forcing and related problems ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ An integer program for positive semidefinite zero forcing in graphs ⋮ Connected power domination in graphs ⋮ Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem

Uses Software

• SteinLib
• OR-Library
• K_TREE/K_SUBGRAPH

Cites Work

• Unnamed Item
• 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
• Revisiting dynamic programming for finding optimal subtrees in trees
• 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
• The Steiner tree polytope and related polyhedra
• Tree polytope on 2-trees
• The volume algorithm revisited: relation with bundle methods
• Solving Steiner tree problems in graphs with Lagrangian relaxation
• Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem
• New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
• Local search algorithms for the \(k\)-cardinality tree problem.
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem
• Solving the Uncapacitated Network Design Problem by a Lagrangean Heuristic and Branch-and-Bound
• Integer Programming Formulation of Traveling Salesman Problems
• Integer Programming Formulations for the k-Cardinality Tree Problem
• Solving the Steiner Tree Problem on a Graph Using Branch and Cut
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• Decomposing Matrices into Blocks
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem
• Solving Steiner tree problems in graphs to optimality
• Validation of subgradient optimization
• Spanning Trees—Short or Small
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation