Integer programming formulations for the k-in-a-tree problem in graphs

DOI10.1111/ITOR.13297MaRDI QIDQ6495390zbMATH OpenFDO

Authors Lucas Saldanha Ferreira, Vinícius F. dos Santos, Cristiano Arbex Valle

Publication date 30 April 2024

Published in International Transactions in Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1111/ITOR.13297

zbMATH Keywords

\(k\)-in-a-treeinduced subgraphsinteger programming

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A faster algorithm to recognize even-hole-free graphs
• A note on the lifted Miller-Tucker-Zemlin subtour elimination constraints for the capacitated vehicle routing problem
• An analytical comparison of different formulations of the travelling salesman problem
• An experimental study of ILP formulations for the longest induced path problem
• Chordless paths through three vertices
• Classification of travelling salesman problem formulations
• Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
• Finding induced trees
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• Maximal Flow Through a Network
• New formulations and branch-and-cut procedures for the longest induced path problem
• On exact solution approaches for the longest induced path problem
• On the complexity of testing for odd holes and induced odd paths
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• Solving Steiner tree problems in graphs to optimality
• Solving the feedback vertex set problem on undirected graphs
• The \(k\)-in-a-path problem for claw-free graphs
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The four-in-a-tree problem in triangle-free graphs
• The three-in-a-tree problem
• The traveling salesman problem: An overview of exact and approximate algorithms

This page was built for publication: Integer programming formulations for the \(k\)-in-a-tree problem in graphs

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