A note on relatives to the Held and Karp 1-tree problem
From MaRDI portal
Publication:2494821
DOI10.1016/j.orl.2005.04.010zbMath1113.90165OpenAlexW1971468650MaRDI QIDQ2494821
Maud Göthe-Lundgren, Torbjörn Larsson, Andreas Westerlund
Publication date: 30 June 2006
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.orl.2005.04.010
vehicle routingtraveling salesmandegree constraintcounter-example1-tree problempolynomial time-complexity
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (3)
Approximation algorithms for constructing spanning \(K\)-trees using stock pieces of bounded length ⋮ A stabilized column generation scheme for the traveling salesman subtour problem ⋮ The \(k\)-path tree matroid and its applications to survivable network design
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
- The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
- Estimating the Held-Karp lower bound for the geometric TSP
- Minimum directed 1-subtree relaxation for score orienteering problem
- Constrained spanning trees and the traveling salesman problem
- Stronger \(K\)-tree relaxations for the vehicle routing problem
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- On the nucleolus of the basic vehicle routing game
- A stabilized column generation scheme for the traveling salesman subtour problem
- Probabilistic Analysis of the Held and Karp Lower Bound for the Euclidean Traveling Salesman Problem
- An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
- An SST-based algorithm for the steiner problem in graphs
- An Optimal Algorithm for the Orienteering Tour Problem
- A good algorithm for smallest spanning trees with a degree constraint
- The Held—Karp algorithm and degree-constrained minimum 1-trees
- An Efficient Algorithm for the Min-Sum Arborescence Problem on Complete Digraphs
- Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees
- A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
- An improved branching rule for the symmetric travelling salesman problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: A note on relatives to the Held and Karp 1-tree problem
