Using basis dependence distance vectors in the modified Floyd-Warshall algorithm

DOI10.1007/S10878-014-9740-2MaRDI QIDQ2355984zbMATH OpenOpenAlexWikidataFDO

Authors Wlodzimierz Bielecki, Krzysztof Kraska, Tomasz Klimek

Publication date 28 July 2015

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s10878-014-9740-2

zbMATH Keywords

arbitrarily nested loopbasis dependence vectorsFloyd-Warshall algorithmparallelizing compilertransitive closure

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Theory of compilers and interpreters (68N20) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Using basis dependence distance vectors to calculate the transitive closure of dependence relations by means of the Floyd-Warshall algorithm
• Cache-Friendly implementations of transitive closure
• scientific article; zbMATH DE number 1849117
• THE JANUS TEST: A HIERARCHICAL ALGORITHM FOR COMPUTING DIRECTION AND DISTANCE VECTORS (EXTENDED VERSION)*
• Shortest path and closure algorithms for banded matrices

Cites work

• A modular static analysis approach to affine loop invariants detection
• Computing the Transitive Closure of a Union of Affine Integer Tuple Relations
• Graph theory
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 17635 (Why is no real title available?)
• scientific article; zbMATH DE number 1772585 (Why is no real title available?)
• scientific article; zbMATH DE number 2204782 (Why is no real title available?)
• Iterating Octagons
• On computing the transitive closure of a relation
• On multiprocessor system scheduling
• Scheduling problems in a practical allocation model
• The algorithm design manual

Cited in

(1)

• Using basis dependence distance vectors to calculate the transitive closure of dependence relations by means of the Floyd-Warshall algorithm

Describes a project that uses

Uses Software

• Omega
• Stony Brook
• isl

This page was built for publication: Using basis dependence distance vectors in the modified Floyd-Warshall algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2355984)