The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
From MaRDI portal
Publication:987675
DOI10.1016/j.dam.2009.01.017zbMath1231.05139OpenAlexW2045428711MaRDI QIDQ987675
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
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
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
