scientific article; zbMATH DE number 3795354

zbMath0504.68023MaRDI QIDQ4741699

Bernd Mahr

Publication date: 1982

Full work available at URL: https://eudml.org/doc/92166

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

independencelower boundsalgebraic complexitypath problemssemi-ringsstraightline programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semirings (16Y60)

Cites Work

• Shortest-path problem is not harder than matrix multiplication
• Linear and combinatorial optimization in ordered algebraic structures
• Algebraic structures for transitive closure
• Shortest-path algorithms: Taxonomy and annotation
• A Shortest-Path Algorithm with Expected Time $O(n^2 \log n\log ^ * n)$
• The Power of Negative Thinking in Multiplying Boolean Matrices
• On Finding and Updating Spanning Trees and Shortest Paths
• New Bounds on the Complexity of the Shortest Path Problem
• A Shortest Path Algorithm for Edge-Sparse Graphs
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item