Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 DetailsÜbersicht
  Traveling Salesman-Based Curve Reconstruction in Polynomial Time

Althaus, E., & Mehlhorn, K. (2001). Traveling Salesman-Based Curve Reconstruction in Polynomial Time. SIAM Journal on Computing, 31, 27-66.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-313D-6 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-313E-4
Genre: Zeitschriftenartikel

Dateien

einblenden: Dateien
ausblenden: Dateien
:
143.pdf (beliebiger Volltext), 577KB
 
Datei-Permalink:
-
Name:
143.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-
:
Mehlhorn_a_2001_j.pdf (beliebiger Volltext), 623KB
 
Datei-Permalink:
-
Name:
Mehlhorn_a_2001_j.pdf
Beschreibung:
-
OA-Status:
Sichtbarkeit:
Privat
MIME-Typ / Prüfsumme:
application/pdf
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-
Lizenz:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Althaus, Ernst1, Autor           
Mehlhorn, Kurt1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: An instance of the curve reconstruction problem is a finite sample set $V$ of an unknown curve $\gamma$. The task is to connect the points in $V$ in the order in which they lie on $\gamma$. Giesen~\cite{Giesen:TSP} showed recently that the Traveling Salesman tour of $V$ solves the reconstruction problem under fairly week assumptions on $\gamma$ and $V$. We extend his result along three dimensions. We weaken the assumptions, give an alternate proof, and show that in the context of curve reconstruction, the Traveling Salesman tour can be constructed in polynomial time.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2006-11-092001
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 344456
Anderer: Local-ID: C1256428004B93B8-7C04B324978725EFC1256A8E0064302F-AltMeh2001j
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: SIAM Journal on Computing
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 31 Artikelnummer: - Start- / Endseite: 27 - 66 Identifikator: ISSN: 0097-5397