On the graph turnpike problem

Tomás Feder; Rajeev Motwani

doi:10.1016/j.ipl.2009.03.024

On the graph turnpike problem

Tomás Feder, Rajeev Motwani

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	774-776
Number of pages	3
Journal	Information Processing Letters
Volume	109
Issue number	14
DOIs	https://doi.org/10.1016/j.ipl.2009.03.024
State	Published - Jun 2009
Externally published	Yes

Bibliographical note

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.

Access to Document

10.1016/j.ipl.2009.03.024

Cite this

@article{f410f393051d438699e827d760023702,

title = "On the graph turnpike problem",

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.",

author = "Tom{\'a}s Feder and Rajeev Motwani",

note = "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.",

year = "2009",

month = jun,

doi = "10.1016/j.ipl.2009.03.024",

language = "English (US)",

volume = "109",

pages = "774--776",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "14",

}

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

SN - 0020-0190

VL - 109

SP - 774

EP - 776

JO - Information Processing Letters

JF - Information Processing Letters

IS - 14

ER -

On the graph turnpike problem

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this