Semi-preemptive routing on a line

Räbiger, Dirk (2004) Semi-preemptive routing on a line.
Published in: Electronic Notes in Discrete Mathematics Vol. 17. pp. 241-246.


The problem of routing a robot (or vehicle) between n stations in the plane in order to transport objects is well studied, even if the stations are specially arranged, e.g. on a linear track or circle. The robot may use either all or none of the stations for reloading. We will generalize these concepts of preemptiveness/non--preemptiveness and emancipate the robot by letting it choose k<=n reload--stations.

Download: [img] Postscript - Preprinted Version
Download (278kB) | Preview
Download: [img] PDF - Preprinted Version
Download (110kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2004-466
Depositing User: Dirk Räbiger
Date Deposited: 25 Nov 2004 00:00
Last Modified: 19 Dec 2011 09:44