A new approach to all-pairs shortest paths on real-weighted graphs
type: Item
instance of: scholarly article
title: A new approach to all-pairs shortest paths on real-weighted graphs
zbMATH Open document ID: 1071.68084
DOI: 10.1016/S0304-3975(03)00402-X
author: Seth Pettie
published in: Theoretical Computer Science
publication date: 2004-10-27T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 2110970
zbMATH Keywords: Comparison-addition model
zbMATH Keywords: All-pairs shortest paths
zbMATH Keywords: Real weights
Wikidata QID: Q56078250
MaRDI profile type: Publication
cites work: Faster algorithms for the shortest path problem
cites work: On the exponent of all pairs shortest path problem
cites work: A minimum spanning tree algorithm with inverse-Ackermann type complexity
cites work: Introduction to algorithms
cites work: A note on two problems in connexion with graphs
cites work: New Bounds on the Complexity of the Shortest Path Problem
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: Faster Scaling Algorithms for Network Problems
cites work: All pairs shortest distances for graphs with small integer length edges
cites work: Scaling Algorithms for the Shortest Paths Problem
cites work: Information Bounds Are Weak in the Shortest Distance Problem
cites work: Improved fast integer sorting in linear space
cites work: Deterministic sorting in O ( n log log n ) time and linear space
cites work: Q2754134
cites work: Efficient Algorithms for Shortest Paths in Sparse Networks
cites work: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
cites work: Finding Real-Valued Single-Source Shortest Paths ino(n3) Expected Time
cites work: Q4425938
cites work: An optimal minimum spanning tree algorithm
cites work: Q4707795
cites work: Q4828943
cites work: On the all-pairs-shortest-path problem in unweighted undirected graphs.
cites work: On Finding and Updating Spanning Trees and Shortest Paths
cites work: A class of algorithms which require nonlinear time to maintain disjoint sets
cites work: A new upper bound on the complexity of the all pairs shortest path problem
cites work: Undirected single-source shortest paths with positive integer weights in linear time
cites work: Integer priority queues with decrease key in constant time and the single source shortest paths problem
cites work: Design and implementation of an efficient priority queue
cites work: Q4796165
cites work: All pairs shortest paths using bridging sets and rectangular matrix multiplication
DBLP publication ID: journals/tcs/Pettie04
description: scientific article; zbMATH DE number 2110970