Name
Abstract | ||
|---|---|---|
We propose an exact algorithm for solving the longest simple 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. Lastly, we present a scalable parallelization which yields the first efficient parallel algorithm for the problem. |
Year | Venue | Field |
|---|---|---|
2019 | SOCS | Dynamic programming,Discrete mathematics,Graph,Path (graph theory),Exact algorithm,Vertex (geometry),Parallel algorithm,Algorithm,Graph partition,Mathematics,Scalability |
DocType | Volume | Citations |
Journal | abs/1905.03645 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kai Fieger | 1 | 0 | 0.68 |
| Tomás Balyo | 2 | 0 | 0.34 |
| Christian Schulz | 3 | 240 | 24.10 |
| Dominik Schreiber | 4 | 0 | 0.68 |