A Polynomial Algorithm for the Degree-Constrained Minimum K-Tree Problem
Operations Research · 1994 · Volume 42 · Issue 4
Abstract
Given a graph with n + 1 nodes, a K -tree is defined to be a set of n + K edges that span the graph. This paper presents an algorithm for finding a minimum cost K -tree with a specified degree at a designated node. The algorithm runs in O ( n 3 ) time and is useful in the optimal solution of certain Lagrangian relaxations arising in vehicle routing.
Keywords
networks/graphs, tree algorithms: minimum k-tree algorithms, transportation, vehicle routing: optimization algorithm
Enable JavaScript for citation tools and additional paper interactions.