A POLYNOMIAL ALGORITHM FOR THE DEGREE-CONSTRAINED MINIMUM K-TREE PROBLEM
成果类型：
Article
署名作者：
FISHER, ML
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.4.775
发表日期：
1994
页码：
775-779
关键词：
摘要：
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 is paper presents an algorithm for finding a minimum cost K-tree with a specified degree at a designated node. The algorithm runs in O(n3) time and is useful in the optimal solution of certain Lagrangian relaxations arising in vehicle routing.