KIT | KIT-Bibliothek | Impressum | Datenschutz

Finding Optimal Longest Paths by Dynamic Programming in Parallel

Fieger, Kai 1; Balyo, Tomáš 1; Schulz, Christian; Schreiber, Dominik 1
1 Karlsruher Institut für Technologie (KIT)

We propose an exact algorithm for solving the longest path problem between two given vertices in undirected weighted graphs. By using graph partitioning and dynamic programming, we obtain an algorithm that is significantly faster than other state-of-the-art methods. This enables us to solve instances that were previously unsolved and solve hard instances significantly faster. We also present a parallel version of the algorithm.

Zitationen: 4
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2019
Sprache Englisch
Identifikator ISBN: 978-1-57735-808-4
KITopen-ID: 1000097227
Erschienen in Proceedings of the 12th Annual Symposium on Combinatorial Search (SoCs 2019), Napa, CA, July 16-17, 2019
Veranstaltung 12th Annual Symposium on Combinatorial Search (SoCs 2019), Napa, CA, USA, 16.07.2019 – 17.07.2019
Verlag AAAI Press
Seiten 61-69
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page