A POLYNOMIAL ALGORITHM FOR THE DEGREE-CONSTRAINED MINIMUM K-TREE PROBLEM

被引：16

作者：

FISHER, ML

机构：

[1] Univ of Pennsylvania, Philadelphia, PA

来源：

OPERATIONS RESEARCH | 1994年 / 42卷 / 04期

关键词：

D O I：

10.1287/opre.42.4.775

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：775 / 779

页数：5