scientific article; zbMATH DE number 4031431

From MaRDI portal
Publication:3771995





[For the entire collection see Zbl 0627.00024.] Bei einer optimalen Travelling-Salesman-Tour werden bei zwei Transformationen des Datensatzes die Bedingungen untersucht, unter denen die Optimalität der Rundreise erhalten bleibt. Unter den Knoten des Datensatzes wird ein Knoten der optimalen Tour gestrichen (Kontraktion), und zu den n Knoten des Datensatzes wird ein zusätzlicher Knoten hinzugefügt (Expansion). Diese Art der Untersuchung erstreckt sich auf symmetrische Distanzmatrizen, wobei abstrakte Datensätze und euklidische Datensätze betrachtet werden. Im euklidischen Fall werden allgemeine Aussagen zur Gestalt der optimalen Tour und eine schnelle Heuristik hergeleitet.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3771995)