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

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

doi:10.1137/S0097539796303421

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

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	1167-1181
Number of pages	15
Journal	SIAM Journal on Computing
Volume	28
Issue number	4
DOIs	https://doi.org/10.1137/S0097539796303421
State	Published - 1999
Externally published	Yes

ASJC Scopus subject areas

Computer Science(all)
Mathematics(all)

Online availability

10.1137/S0097539796303421

Library availability

Discover UIUC Full Text

Cite this

@article{f1c38ed504e24d09b69c748d454c5a38,

title = "Fast estimation of diameter and shortest paths (without matrix multiplication)",

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.",

author = "D. Aingworth and C. Chekuri and P. Indyk and R. Motwani",

year = "1999",

doi = "10.1137/S0097539796303421",

language = "English (US)",

volume = "28",

pages = "1167--1181",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

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

AU - Aingworth, D.

AU - Chekuri, C.

AU - Indyk, P.

AU - Motwani, R.

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032657365&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032657365&partnerID=8YFLogxK

U2 - 10.1137/S0097539796303421

DO - 10.1137/S0097539796303421

M3 - Article

AN - SCOPUS:0032657365

SN - 0097-5397

VL - 28

SP - 1167

EP - 1181

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

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

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this