<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Scaling Algorithms for the Shortest Paths Problem

Name: Scaling Algorithms for the Shortest Paths Problem
Creator: Andrew V. Goldberg
Keywords: scaling algorithms, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Analysis of algorithms and problem complexity, Graph theory (including graph drawing) in computer science, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Parallel algorithms in computer science, shortest paths problem, 01 natural sciences

Scaling algorithms for the shortest paths problem

descriptionPublicationkeyboard_double_arrow_right Article 01 Jun 1995Publisher:Society for Industrial & Applied Mathematics (SIAM)Journal:SIAM Journal on Computing, volume 24, pages 494-504 (issn: 0097-5397, eissn: 1095-7111,

Authors: Andrew V. Goldberg;

doi: 10.1137/s0097539792231179 , 10.5555/313559.313756

Scaling Algorithms for the Shortest Paths Problem

- Summary
- Subjects
- Metrics

Abstract

Summary: We describe a new method for designing scaling algorithms for the single- source shortest paths problem and use this method to obtain an \(O (\sqrt nm \log N)\) algorithm for the problem. (Here \(n\) and \(m\) are the number of nodes and arcs in the input network and \(N\) is essentially the absolute value of the most negative arc length: arc lengths are assumed to be integral.) This improves previous bounds for the problem. The method extends to related problems.

Related Organizations

Stanford University
United States

Keywords

scaling algorithms, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), Analysis of algorithms and problem complexity, Graph theory (including graph drawing) in computer science, Parallel algorithms in computer science, shortest paths problem

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	112
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 1%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%