I/O-efficient Hierarchical Diameter Approximation

Files in This Item:
File Description SizeFormat 
ajwani_esa12.pdf189.27 kBAdobe PDFDownload
Title: I/O-efficient Hierarchical Diameter Approximation
Authors: Ajwani, Deepak
Meyer, Ulrich
Veith, David
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 [17] 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 memoryApproximation ratioInput graphExternal memoryGraph 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

Citations 50

Last Week
Last month
checked on May 17, 2019

Google ScholarTM



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.