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 |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=182365555&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 182365555 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00010782 ACM jtl: Communications of the ACM issn: 00010782 maglogo: N pubinfo: dt: Feb2025 vid: 68 iid: 2 pid: 68 pub: Association for Computing Machinery artinfo: ui: 182365555 10.1145/3660528 ppf: 86 ppct: 1 formats: tig: atl: Shortening the Path to Designing Efficient Graph Algorithms. aug: au: Peng, Richard affil: Carnegie Mellon University, School of Computer Science, Pittsburgh, PA, USA su: Graph algorithms Graph theory Directed graphs Mathematical optimization Undirected graphs sug: subj: Graph algorithms Graph theory Directed graphs Mathematical optimization Undirected graphs ab: 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. pubtype: Periodical doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2025 holdings: @attributes: islocal: N |
|---|