Name
Abstract | ||
|---|---|---|
We consider the problem of computing a minimum-weight polygonal path between two points in a weighted polygonal subdivision,
subject to the constraint that the path have few segments (links). We give an algorithm that generates paths of weighted length at most (1 + ε) times the weight of a minimum-cost k-link path, for any fixed ε> 0, while using at most 2k − 1 links. This is an improvement over the previous (1 + ε)-approximation algorithm, which used at most 5k − 2 links. Further, we have implemented our new algorithm and we have conducted a performance study of these algorithms (old
and new) on a variety of real-world and synthetic data, comparing not only the efficiency but also the quality of paths generated
using these algorithms. We also consider the implications of these results on the practical usage of these algorithms.
|
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/978-3-540-68405-3_12 | WAFR |
Keywords | Field | DocType |
synthetic data,shortest path algorithm | Mathematical optimization,Shortest path problem,Computer science,Algorithm,Constrained Shortest Path First,Yen's algorithm,Floyd–Warshall algorithm,Shortest Path Faster Algorithm,Longest path problem,Widest path problem,K shortest path routing | Conference |
Citations | PageRank | References |
1 | 0.37 | 14 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ovidiu Daescu | 1 | 276 | 45.78 |
| Joseph S.B. Mitchell | 2 | 4329 | 428.84 |
| Simeon C. Ntafos | 3 | 599 | 98.18 |
| James D. Palmer | 4 | 53 | 14.93 |
| Chee-Keng Yap | 5 | 1996 | 395.32 |