The k-Cardinality Tree Problem: reformulations and Lagrangian relaxation
From MaRDI portal
Publication:987675
DOI10.1016/J.DAM.2009.01.017zbMATH Open1231.05139OpenAlexW2045428711MaRDI QIDQ987675FDOQ987675
Authors: 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
Recommendations
- New branch-and-bound algorithms for \(k\)-cardinality tree problems
- Integer Programming Formulations for the k-Cardinality Tree Problem
- Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
- scientific article; zbMATH DE number 1195632
- Weighted k‐cardinality trees: Complexity and polyhedral structure
Linear programming (90C05) Trees (05C05) Extremal problems in graph theory (05C35) Integer programming (90C10)
Cites Work
- Solving Steiner tree problems in graphs to optimality
- \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Integer Programming Formulation of Traveling Salesman Problems
- Solution of a Large-Scale Traveling-Salesman Problem
- Tree polytope on 2-trees
- Solving the uncapacitated network design problem by a Lagrangean heuristic and branch-and-bound
- Title not available (Why is that?)
- Validation of subgradient optimization
- Local search algorithms for the \(k\)-cardinality tree problem.
- Decomposing Matrices into Blocks
- The Steiner tree polytope and related polyhedra
- Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
- New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
- Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
- A Lagrangian Heuristic Based Branch-and-Bound Approach for the Capacitated Network Design Problem
- Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem
- Integer Programming Formulations for the k-Cardinality Tree Problem
- The volume algorithm revisited: relation with bundle methods
- Spanning Trees—Short or Small
- An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
- Title not available (Why is that?)
- Title not available (Why is that?)
- New metaheuristic approaches for the edge-weighted \(k\)-cardinality tree problem
- Solving the Steiner Tree Problem on a Graph Using Branch and Cut
- Weighted k‐cardinality trees: Complexity and polyhedral structure
- Solving Steiner tree problems in graphs with Lagrangian relaxation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Integer programming approaches to facilities layout models with forbidden areas
- Revisiting dynamic programming for finding optimal subtrees in trees
- Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem
Cited In (9)
- Connected power domination in graphs
- Integer Programming Formulations for the k-Cardinality Tree Problem
- Computational approaches for zero forcing and related problems
- On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
- New branch-and-bound algorithms for \(k\)-cardinality tree problems
- Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
- Extended formulations for the cardinality constrained subtree of a tree problem
- Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
- An integer program for positive semidefinite zero forcing in graphs
Uses Software
This page was built for publication: The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987675)
