Fast dynamic transitive closure with lookahead

DOI10.1007/s00453-008-9166-2zbMath1191.68855OpenAlexW2090263269MaRDI QIDQ848959

Marcin Mucha, Piotr Sankowski

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9166-2

zbMATH Keywords

planar graphstransitive closuredynamic algorithmsalgebraic algorithmsmatrix inverselookahead

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (3)

Fast matrix multiplication and its algebraic neighbourhood ⋮ Sharing the cost of maximum quality optimal spanning trees ⋮ Dynamic matrix rank with partial lookahead

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matrix multiplication via arithmetic progressions
• Fast rectangular matrix multiplication and applications
• Rectangular matrix multiplication revisited
• On certificates and lookahead in dynamic graph problems
• Improved Dynamic Reachability Algorithms for Directed Graphs
• A fully dynamic reachability algorithm for directed graphs with an almost linear update time
• Generalized Nested Dissection
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• An On-Line Edge-Deletion Problem
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• A fully dynamic algorithm for maintaining the transitive closure

This page was built for publication: Fast dynamic transitive closure with lookahead