Shortening the Path to Designing Efficient Graph Algorithms.
This paper introduces a nearly linear-time algorithm for solving the negative weighted shortest-path problem in directed graphs without converting them to undirected counterparts, a departure from traditional approaches. By leveraging advanced graph decomposition techniques, it demonstrates that eff...
| Publicado en: | Communications of the ACM Vol. 68; no. 2; pp. 86 - 87 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Association for Computing Machinery
Feb2025
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| Sumario: | This paper introduces a nearly linear-time algorithm for solving the negative weighted shortest-path problem in directed graphs without converting them to undirected counterparts, a departure from traditional approaches. By leveraging advanced graph decomposition techniques, it demonstrates that efficient algorithms can be developed while working exclusively within the framework of directed graphs. This breakthrough not only addresses a longstanding challenge in graph theory but also provides a foundation for designing efficient algorithms for other complex directed graph problems. |
|---|