I/O-efficient Hierarchical Diameter Approximation
|Title:||I/O-efficient Hierarchical Diameter Approximation||Authors:||Ajwani, Deepak
|Permanent link:||http://hdl.handle.net/10197/9897||Date:||Oct-2012||Online since:||2019-04-10T12:04:00Z||Abstract:||Computing diameters of huge graphs is a key challenge in complex network analysis. As long as the graphs fit into main memory, diameters can be efficiently approximated (and frequently even exactly determined) using heuristics that apply a limited number of BFS traversals. If the input graphs have to be kept and processed on external storage, even a single BFS run may cause an unacceptable amount of time-consuming I/O-operations. Meyer  proposed the first parameterized diameter approximation algorithm with fewer I/Os than that required for exact BFS traversal. In this paper we derive hierarchical extensions of this randomized approach and experimentally compare their trade-offs between actually achieved running times and approximation ratios. We show that the hierarchical approach is frequently capable of producing surprisingly good diameter approximations in shorter time than BFS. We also provide theoretical and practical insights into worst-case input classes.||Type of material:||Conference Publication||Publisher:||Springer||Series/Report no.:||Lecture Notes in Computer Science (LCNS, volume 7501)||Copyright (published version):||2012 Springer||Keywords:||Main memory; Approximation ratio; Input graph; External memory; Graph class||DOI:||10.1007/978-3-642-33090-2_8||Other versions:||http://algo12.fri.uni-lj.si/?file=about||Language:||en||Status of Item:||Peer reviewed||Is part of:||Epstein, L., Ferragina, P. Algorithms - ESA 2012: 20th Annual European Symposium Ljubjana, Slovenia, September 10-12, 2012: Proceedings||Conference Details:||The 20th Annual European Symposium, Ljubljana, Slovenia, 10-12 September 2012||ISBN:||9783642330896|
|Appears in Collections:||Computer Science Research Collection|
Show full item record
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.