Concepedia

Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths

Surender Baswana, Ramesh Hariharan, Sandeep Sen

Journal of Algorithms · 2004 · 57 citations · 14 references

Concepts

ComputingComputer ScienceAlgorithmsCombinatoricsComputational GeometryAlgorithm AnalysisGraph AlgorithmsShortest Path AlgorithmsTime ComplexityAll-pairs Shortest PathsAmortized Running TimeComputational Complexity Of Graph AlgorithmsDecremental Shortest Path AlgorithmsDeletion AlgorithmsShortest Path In Undirected GraphsShortest PathsTransitive Closure

References

14

Matrix multiplication via arithmetic progressions

Don Coppersmith, S. Winograd · Journal of Symbolic Computation · 1990 · 2.3K citations

Computing, Computer Science, Mathematics +14

Filtering Search: A New Approach to Query-Answering

Bernard Chazelle · SIAM Journal on Computing · 1986 · 300 citations

Computing, Computer Science, Algorithms +10

An On-Line Edge-Deletion Problem

Yossi Shiloach, Shimon Even · Journal of the ACM · 1981 · 284 citations

Computing, Computer Science, Information Retrieval +5

Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs

Valerie King · 2003 · 228 citations

Computing, Computer Science, Algorithms +14

A compression technique to materialize transitive closure

H. V. Jagadish · ACM Transactions on Database Systems · 1990 · 179 citations · Full text

Computing, Computer Science, Data Management +15