Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) Export

@inproceedings{citeulike:2813688, abstract = {In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths problem running in time significantly smaller than the obvious time bound of O(n\³). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that...}, author = {Aingworth and Chekuri and Motwani}, booktitle = {SODA: {ACM}-{SIAM} Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms)}, citeulike-article-id = {2813688}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6559}, keywords = {all-pairs-shortest-paths, centrality, social, social-networks, yrbcn}, posted-at = {2008-05-19 18:15:31}, priority = {2}, title = {Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6559}, year = {1996} }

TY - CONF ID - citeulike:2813688 L3 - citeulike-article-id:2813688 N2 - In the recent past, there has been considerable progress in devising algorithms for the all-pairs shortest paths problem running in time significantly smaller than the obvious time bound of O(n³). Unfortunately, all the new algorithms are based on fast matrix multiplication algorithms that are notoriously impractical. Our work is motivated by the goal of devising purely combinatorial algorithms that match these improved running times. Our results come close to achieving this goal, in that... TI - Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) T2 - SODA: {ACM}-{SIAM} Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms) KW - all-pairs-shortest-paths KW - centrality KW - social KW - social-networks KW - yrbcn AU - Aingworth AU - Chekuri AU - Motwani PY - 1996/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.6559 ER -