Cover Image
QR Code

Negative-Weight Single-Source Shortest Paths in Near-Linear Time.

In this research article, the authors present a simple combinatorial algorithm that reduces running time to near-linear to address the single-source shortest paths problem. The authors present two questions-- including can the algorithm perform without complex machinery-- and five theorems--that dea...

Full description

Published in:Communications of the ACM Vol. 68; no. 2; pp. 87 - 95
Main Authors: Bernstein, Aaron, Nanongkai, Danupon, Wulff-Nilsen, Christian
Format: Article
Published: Association for Computing Machinery Feb2025
Subjects:
Algorithms
Weighted graphs
Directed graphs
Graph algorithms
Graph theory
Decomposition method
Online Access:View this record in EBSCOhost
fields @attributes:
  recordID: 1
pdfLink:
plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=182365553&site=ehost-live
header:
  @attributes:
    shortDbName: hlh
    uiTerm: 182365553
    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:
        182365553
        10.1145/3631536
      ppf: 87
      ppct: 8
      formats:
      tig:
        atl: Negative-Weight Single-Source Shortest Paths in Near-Linear Time.
      aug:
        au:
          Bernstein, Aaron
          Nanongkai, Danupon
          Wulff-Nilsen, Christian
        affil:
          Rutgers University, New Brunswick, NJ, USA
          Max Planck Institute for Informatics, Munich, Germany
          Independent, Copenhagen, Denmark
      su:
        Algorithms
        Weighted graphs
        Directed graphs
        Graph algorithms
        Graph theory
        Decomposition method
      sug:
        subj:
          Algorithms
          Weighted graphs
          Directed graphs
          Graph algorithms
          Graph theory
          Decomposition method
      ab: In this research article, the authors present a simple combinatorial algorithm that reduces running time to near-linear to address the single-source shortest paths problem. The authors present two questions-- including can the algorithm perform without complex machinery-- and five theorems--that deal with negative-weight cycle-- in this research and evaluate two algorithms, ScaleDown and the simpler SPMain, in regards to these. Topics include price functions and low-diameter decomposition.
      pubtype: Periodical
      doctype: Article
      src: R
    language: English
    refInfo:
    copyright:
      @attributes:
        flag: Y
      dt:
        @attributes:
          year: 2025
    holdings:
      @attributes:
        islocal: N