The point-to-point delivery and connection problems : complexity and algorithms

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

26 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)267-292
Journal / PublicationDiscrete Applied Mathematics
Volume36
Issue number3
Publication statusPublished - 28 May 1992
Externally publishedYes

Abstract

We consider the computational complexity of point-to-point delivery problems. These problems involve shipping one item from each one of p sources to p destinations might be prematched to sources (the fixed destination case), or a source's item might go to any destination (the nonfixed destination case). The networks can be directed or undirected. Up to K items at once can share a truck on an arc, and costs are linear in the number of trucks used. We also consider the closely related point-to-point connection problems, which are to find a minimum cost arc subset connecting sources with destinations. We find that all variations of both problems are strongly NP-hard for all K≤2, but that there are polynomial algorithms in some cases if p is fixed, or if the underlying network is a grid with sources on one side, destinations on the other. © 1992.

Bibliographic Note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Citation Format(s)

The point-to-point delivery and connection problems: complexity and algorithms. / Li, Chung-Lun; McCormick, S.Thomas; Simchi-Levi, David.
In: Discrete Applied Mathematics, Vol. 36, No. 3, 28.05.1992, p. 267-292.

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review