On the graph turnpike problem

Tomás Feder, Rajeev Motwani

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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 languageEnglish (US)
Pages (from-to)774-776
Number of pages3
JournalInformation Processing Letters
Volume109
Issue number14
DOIs
StatePublished - Jun 2009
Externally publishedYes

Fingerprint Dive into the research topics of 'On the graph turnpike problem'. Together they form a unique fingerprint.

Cite this