Fast estimation of diameter and shortest paths (without matrix multiplication)

D. Aingworth, C. Chekuri, P. Indyk, R. Motwani

Research output: Contribution to journalArticlepeer-review

Abstract

A study is carried out to devise purely combinatorial algorithms that match improved running times. Algorithms with small additive error in the length of the paths obtained are presented. The algorithms are easy to implement, have the desired property of being combinatorial in nature, and the hidden constants in the running time bound are fairly small.

Original languageEnglish (US)
Pages (from-to)1167-1181
Number of pages15
JournalSIAM Journal on Computing
Volume28
Issue number4
DOIs
StatePublished - 1999
Externally publishedYes

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics

Fingerprint

Dive into the research topics of 'Fast estimation of diameter and shortest paths (without matrix multiplication)'. Together they form a unique fingerprint.

Cite this