A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs

DOI10.1007/978-3-642-27660-6_31zbMath1302.05194arXiv1111.6519OpenAlexW3124258952MaRDI QIDQ2891383

Dzmitry Sledneu, Andrzej Lingas

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1111.6519

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items (max. 100)

Efficient parameterized algorithms for computing all-pairs shortest paths ⋮ 3D rectangulations and geometric matrix multiplication

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Fast rectangular matrix multiplication and applications
• On the exponent of all pairs shortest path problem
• Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
• Efficient determination of the transitive closure of a directed graph
• Fly Cheaply: On the Minimum Fuel Consumption Problem
• More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Fast recognition of pushdown automaton and context-free languages
• Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces
• Regularity Lemmas and Combinatorial Algorithms
• Approximate Distance Queries in Disk Graphs
• Subquadratic approximation algorithms for clustering problems in high dimensional spaces
• Algorithms and Data Structures

This page was built for publication: A Combinatorial Algorithm for All-Pairs Shortest Paths in Directed Vertex-Weighted Graphs with Applications to Disc Graphs