Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

DOI10.4230/LIPIcs.ICALP.2018.44zbMath1499.68265OpenAlexW2886888786MaRDI QIDQ5002719

Yong Gu, Le Zhang, Ran Duan

Publication date: 28 July 2021

Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2018/9048/

zbMATH Keywords

graph algorithmsmatrix multiplicationnon-decreasing paths

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A simple approach to nondecreasing paths ⋮ Faster Algorithms for All Pairs Non-Decreasing Paths Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• All-pairs bottleneck paths in vertex weighted graphs
• On the all-pairs-shortest-path problem in unweighted undirected graphs.
• All pairs shortest paths for graphs with small integer length edges
• On the exponent of all pairs shortest path problem
• All pairs shortest distances for graphs with small integer length edges
• A shortest cycle for each vertex of a graph
• Faster algorithms for finding lowest common ancestors in directed acyclic graphs
• Finding a maximum weight triangle in n ^3-Δ time, with applications
• On the Shoshan-Zwick Algorithm for the All-Pairs Shortest Path Problem
• Algorithmic Applications of Baur-Strassen’s Theorem
• Powers of tensors and fast matrix multiplication
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems
• Improved Distance Queries and Cycle Counting by Frobenius Normal Form
• Fibonacci heaps and their uses in improved network optimization algorithms
• Letter to the Editor—A Variant on the Shortest-Route Problem
• Multiplying matrices faster than coppersmith-winograd
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms

This page was built for publication: Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs