Scaling Algorithms for the Shortest Paths Problem,

Abstract

We give an O((square root of n)m log N) algorithm for the single-source shortest paths problem with integral arc lengths. (Here n and m is the number of nodes and arcs in the input network and N is essentially the absolute value of the most negative arc length.) This improves previous bounds for the problem.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1992
Accession Number
ADA322745

Entities

People

  • Andrew N. Goldberg

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Integrals
  • Iterations
  • Mathematics
  • Procedures (Computers)
  • Security
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.