> Detailanzeige

Mamano, Nil [Verfasser:in]; Efrat, Alon [Verfasser:in]; Eppstein, David [Verfasser:in]; Frishberg, Daniel [Verfasser:in]; Goodrich, Michael T. [Verfasser:in]; Kobourov, Stephen [Verfasser:in]; Matias, Pedro [Verfasser:in]; Polishchuk, Valentin [Verfasser:in] ; Nil Mamano and Alon Efrat and David Eppstein and Daniel Frishberg and Michael T. Goodrich and Stephen Kobourov and Pedro Matias and Valentin Polishchuk [Mitwirkende:r]

New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht
  • Titel: New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs
  • Beteiligte: Mamano, Nil [Verfasser:in]; Efrat, Alon [Verfasser:in]; Eppstein, David [Verfasser:in]; Frishberg, Daniel [Verfasser:in]; Goodrich, Michael T. [Verfasser:in]; Kobourov, Stephen [Verfasser:in]; Matias, Pedro [Verfasser:in]; Polishchuk, Valentin [Verfasser:in]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.ISAAC.2019.51
  • Schlagwörter: Nearest-neighbors ; Steiner TSP ; Nearest-neighbor chain ; straight skeleton ; multi-fragment algorithm ; Euclidean TSP ; motorcycle graph
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: We show new applications of the nearest-neighbor chain algorithm, a technique that originated in agglomerative hierarchical clustering. We use it to construct the greedy multi-fragment tour for Euclidean TSP in O(n log n) time in any fixed dimension and for Steiner TSP in planar graphs in O(n sqrt(n)log n) time; we compute motorcycle graphs, a central step in straight skeleton algorithms, in O(n^(4/3+epsilon)) time for any epsilon>0.
  • Zugangsstatus: Freier Zugang