Polyhedral results and a branch-and-cut algorithm for the k-cardinality tree problem

DOI10.1007/S10107-012-0590-3MaRDI QIDQ2434979zbMATH OpenOpenAlexFDO

Authors L. Simonetti, Alexandre Salles da Cunha, Abilio Lucena

Publication date 3 February 2014

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10107-012-0590-3

zbMATH Keywords

\(k\)-cardinality tree problembranch-and-cut algorithmpolyhedral study

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• New branch-and-bound algorithms for k-cardinality tree problems
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Obtaining Optimalk-Cardinality Trees Fast
• Obtaining optimal \(k\)-cardinality trees fast
• scientific article; zbMATH DE number 764407

Cites work

• \(K\)-tree/\(K\)-subgraph: A program package for minimal weighted \(K\)-cardinlity trees and subgraphs
• A branch and cut algorithm for the Steiner problem in graphs
• A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An O\((\log k)\)-approximation algorithm for the \(k\) minimum spanning tree problem in the plane
• An SST-based algorithm for the steiner problem in graphs
• Decomposing Matrices into Blocks
• scientific article; zbMATH DE number 4010182 (Why is no real title available?)
• scientific article; zbMATH DE number 193411 (Why is no real title available?)
• scientific article; zbMATH DE number 1195632 (Why is no real title available?)
• scientific article; zbMATH DE number 1215044 (Why is no real title available?)
• scientific article; zbMATH DE number 1263203 (Why is no real title available?)
• Improved algorithms for the Steiner problem in networks
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer programming approaches to facilities layout models with forbidden areas
• Integer Programming Formulation of Traveling Salesman Problems
• Local search algorithms for the \(k\)-cardinality tree problem.
• New branch-and-bound algorithms for k-cardinality tree problems
• New metaheuristic approaches for the edge-weighted k-cardinality tree problem
• Obtaining optimal \(k\)-cardinality trees fast
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Revisiting dynamic programming for finding optimal subtrees in trees
• Solving Steiner tree problems in graphs to optimality
• Spanning Trees—Short or Small
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Upper and lower bounding procedures for minimum rooted \(k\)-subtree problem
• Variable neighborhood search for the vertex weighted \(k\)-cardinality tree problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure

Cited in

(12)

• On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem
• Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem
• New branch-and-bound algorithms for k-cardinality tree problems
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• Integer Programming Formulations for the k-Cardinality Tree Problem
• Weighted k‐cardinality trees: Complexity and polyhedral structure
• scientific article; zbMATH DE number 764407 (Why is no real title available?)
• scientific article; zbMATH DE number 6466099 (Why is no real title available?)
• Obtaining optimal \(k\)-cardinality trees fast
• Solving Steiner trees: Recent advances, challenges, and perspectives
• Polyhedral properties of the \(K\)-median problem on a tree
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation

Describes a project that uses

Uses Software

• K_TREE/K_SUBGRAPH
• SteinLib
• OR-Library

This page was built for publication: Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2434979)