Results on graph turnpike problem without distinctness, including its NP-completeness, and an O(m+n log n) algorithm, is presented. The usual turnpike problem has all pairwise distances given, but does not specify which pair of vertices w e corresponds to. There are two other problems that can be viewed as special cases of the graph turnpike problem, including the bandwidth problem and the low-distortion graph embedding problem. The aim for the turnpike problem in the NP-complete is to orient the edges with weights w i in either direction so that when the whole cycle is transversed in the real line, it returns to a chosen starting point for the cycle. An instance of the turnpike problem with or without distinctness is uniquely mappable if there exists at most one solution up to translation and choice of orientation.
|Original language||English (US)|
|Number of pages||3|
|Journal||Information Processing Letters|
|State||Published - Jun 2009|
Bibliographical noteKAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Supported in part by NSF Grant ITR-0331640, TRUST (NSF award number CCF-0424422), and grants from Cisco, Google, KAUST. Lightspeed. and Microsoft.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.