A NOTE ON THE COMPLEXITY OF A SIMPLE TRANSPORTATION PROBLEM

被引:16
作者
FREDERICKSON, GN
机构
[1] Purdue Univ, West Lafayette, IN
关键词
TRANSPORTATION PROBLEMS; ROBOT ARM MOTION; CIRCULAR TRACK; GRAPH AUGMENTATION;
D O I
10.1137/0222005
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
Consider the problem of using a vehicle to transport k objects one at a time between s stations on a circular track. Let the cost of the transportation be the total distance traveled by the vehicle on the track. An O(k + M (s, q)) time algorithm is presented to find a minimum cost transportation, where M (m, n) is the time to solve a minimum spanning tree problem on a graph with m edges and n vertices, and q less-than-or-equal-to min{k, s} is the number of strongly connected components in an associated balanced problem. Also, the minimum spanning tree problem on a graph with m edges and n vertices is reduced to a transportation problem on a linear track with O(m) stations, O(m) objects, and O(n) strongly connected components in O(m) time.
引用
收藏
页码:57 / 61
页数:5
相关论文
共 6 条