TY - JOUR

T1 - On the graph turnpike problem

AU - Feder, Tomás

AU - Motwani, Rajeev

N1 - KAUST 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.

PY - 2009/6

Y1 - 2009/6

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/599054

UR - https://linkinghub.elsevier.com/retrieve/pii/S0020019009001021

UR - http://www.scopus.com/inward/record.url?scp=67349215036&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2009.03.024

DO - 10.1016/j.ipl.2009.03.024

M3 - Article

VL - 109

SP - 774

EP - 776

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 14

ER -