Traveling in randomly embedded random graphs. Issue 3 (14th December 2018)
- Record Type:
- Journal Article
- Title:
- Traveling in randomly embedded random graphs. Issue 3 (14th December 2018)
- Main Title:
- Traveling in randomly embedded random graphs
- Authors:
- Frieze, Alan
Pegden, Wesley - Abstract:
- Abstract : We consider the problem of traveling among random points in Euclidean space, when only a random fraction of the pairs are joined by traversable connections. In particular, we show a threshold for a pair of points to be connected by a geodesic of length arbitrarily close to their Euclidean distance, and analyze the minimum length Traveling Salesperson Tour, extending the Beardwood‐Halton‐Hammersley theorem to this setting.
- Is Part Of:
- Random structures & algorithms. Volume 55:Issue 3(2019)
- Journal:
- Random structures & algorithms
- Issue:
- Volume 55:Issue 3(2019)
- Issue Display:
- Volume 55, Issue 3 (2019)
- Year:
- 2019
- Volume:
- 55
- Issue:
- 3
- Issue Sort Value:
- 2019-0055-0003-0000
- Page Start:
- 649
- Page End:
- 676
- Publication Date:
- 2018-12-14
- Subjects:
- shortest path -- traveling salesperson problem -- unit square
Random graphs -- Periodicals
Mathematical analysis -- Periodicals
519 - Journal URLs:
- http://onlinelibrary.wiley.com/journal/10.1002/(ISSN)1098-2418 ↗
http://onlinelibrary.wiley.com/ ↗ - DOI:
- 10.1002/rsa.20832 ↗
- Languages:
- English
- ISSNs:
- 1042-9832
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 7254.411950
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 11445.xml