Integer Programming Formulations for the k-Cardinality Tree Problem

DOI10.1016/J.ENDM.2008.01.039MaRDI QIDQ3503557zbMATH OpenOpenAlexFDO

Authors Frederico P. Quintão, Alexandre Salles da Cunha, Geraldo Robson Mateus

Publication date 5 June 2008

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2008.01.039

zbMATH Keywords

\(k\)-cardinality tree probleminteger programmingMiller-Tucker-Zemlin constraints

Mathematics Subject Classification ID

Trees (05C05) Integer programming (90C10)

Recommendations

• Weighted k‐cardinality trees: Complexity and polyhedral structure
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation
• Extended formulations for the cardinality constrained subtree of a tree problem
• New branch-and-bound algorithms for k-cardinality tree problems

Cites work

• scientific article; zbMATH DE number 1195632 (Why is no real title available?)
• scientific article; zbMATH DE number 1215044 (Why is no real title available?)
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• Local branching
• Local search algorithms for the \(k\)-cardinality tree problem.
• 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

(6)

• New branch-and-bound algorithms for k-cardinality tree problems
• Algorithms for the maximum weight connected k-induced subgraph problem
• Looking for edge-equitable spanning trees
• Mathematical programming formulations for the collapsed k-core problem
• Extended formulations for the cardinality constrained subtree of a tree problem
• The \(k\)-Cardinality Tree Problem: reformulations and Lagrangian relaxation

This page was built for publication: Integer Programming Formulations 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 Q3503557)