Publication Details
Title: Preemptive Ensemble Motion Planning on a Tree
Author: G. N. Frederickson and D. J. Guan
Group: ICSI Technical Reports
Date: March 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-011.pdf
Overview:
Consider the problem of transporting a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if objects can be dropped at intermediate vertices along its route and picked up later, then the problem can be solved in polynomial time. Two efficient algorithms are presented for this problem. The first algorithm runs in O(k + qn) time, where n is the number of vertices in the tree, k is the number of objects to be moved, and q is less than or equal to min{k,n} is the number of nontrivial connected components in a related directed graph. The second algorithm runs in O(k + nlogn) time. * Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy.
Bibliographic Information:
ICSI Technical Report TR-89-011
Bibliographic Reference:
G. N. Frederickson and D. J. Guan. Preemptive Ensemble Motion Planning on a Tree. ICSI Technical Report TR-89-011, March 1989
Author: G. N. Frederickson and D. J. Guan
Group: ICSI Technical Reports
Date: March 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-011.pdf
Overview:
Consider the problem of transporting a set of objects between the vertices of a tree by a vehicle that travels along the edges of the tree. The vehicle can carry only one object at a time, and it starts and finishes at the same vertex of the tree. It is shown that if objects can be dropped at intermediate vertices along its route and picked up later, then the problem can be solved in polynomial time. Two efficient algorithms are presented for this problem. The first algorithm runs in O(k + qn) time, where n is the number of vertices in the tree, k is the number of objects to be moved, and q is less than or equal to min{k,n} is the number of nontrivial connected components in a related directed graph. The second algorithm runs in O(k + nlogn) time. * Has since been revised by author. Contact him via "gnf at cs.purdue.edu" for a current copy.
Bibliographic Information:
ICSI Technical Report TR-89-011
Bibliographic Reference:
G. N. Frederickson and D. J. Guan. Preemptive Ensemble Motion Planning on a Tree. ICSI Technical Report TR-89-011, March 1989