GI LogoGI Logo
  • Login
Digital Library
    • All of DSpace

      • Communities & Collections
      • Titles
      • Authors
      • By Issue Date
      • Subjects
    • This Collection

      • Titles
      • Authors
      • By Issue Date
      • Subjects
Digital Library Gesellschaft für Informatik e.V.
GI-DL
    • English
    • Deutsch
  • English 
    • English
    • Deutsch
View Item 
  •   DSpace Home
  • Fachbereiche
  • Technische Informatik (TI)
  • PARS-Mitteilungen
  • PARS-Mitteilungen 2012
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
  •   DSpace Home
  • Fachbereiche
  • Technische Informatik (TI)
  • PARS-Mitteilungen
  • PARS-Mitteilungen 2012
  • View Item

I/O-efficient approximation of graph diameters by parallel cluster growing — a first experimental study

Author:
Ajwani, Deepak [DBLP] ;
Beckmann, Andreas [DBLP] ;
Meyer, Ulrich [DBLP] ;
Veith, David [DBLP]
Abstract
A fundamental step in the analysis of a massive graph is to compute its diameter. In the RAM model, the diameter of a connected undirected unweighted graph can be efficiently 2-approximated using a Breadth-First Search (BFS) traversal from an arbitrary node. However, if the graph is stored on disk, even an external memory BFS traversal is prohibitive, owing to the large number of I/Os it incurs. Meyer [Mey08] proposed a parametrized algorithm to compute an approximation of graph diameter with fewer I/Os than that required for exact BFS traversal of the graph. The approach is based on growing clusters around randomly chosen vertices `in parallel' until their fringes meet. We present an implementation of this algorithm and compare it with some simple heuristics and external-memory BFS in order to determine the trade-off between the approximation ratio and running-time achievable in practice. Our experiments show that with carefully chosen parameters, the new approach is indeed capable to produce surprisingly good diameter approximations in shorter time. We also confirm experimentally, that there are graph-classes where the parametrized approach runs into bad approximation ratios just as the theoretical analysis in [Mey08] suggests.
  • Citation
  • BibTeX
Ajwani, D., Beckmann, A., Meyer, U. & Veith, D., (2012). I/O-efficient approximation of graph diameters by parallel cluster growing — a first experimental study.   PARS: Parallel-Algorithmen, -Rechnerstrukturen und -Systemsoftware: Vol. 29, No. 1. Gesellschaft für Informatik e.V.. (S. 75-86). DOI: 10.1007/BF03342028
@article{mci/Ajwani2012,
author = {Ajwani, Deepak AND Beckmann, Andreas AND Meyer, Ulrich AND Veith, David},
title = {I/O-efficient approximation of graph diameters by parallel cluster growing — a first experimental study},
journal = {PARS},
volume = {},
number = {29, No. 1},
year = {2012},
,
pages = { 75-86 } ,
doi = { 10.1007/BF03342028 }
}
DateienGroesseFormatAnzeige
40731_2014_Article_BF03342028.pdf168.2Kb PDF View/Open

Sollte hier kein Volltext (PDF) verlinkt sein, dann kann es sein, dass dieser aus verschiedenen Gruenden (z.B. Lizenzen oder Copyright) nur in einer anderen Digital Library verfuegbar ist. Versuchen Sie in diesem Fall einen Zugriff ueber die verlinkte DOI: 10.1007/BF03342028

Haben Sie fehlerhafte Angaben entdeckt? Sagen Sie uns Bescheid: Send Feedback

More Info

DOI: 10.1007/BF03342028
ISSN: 0177-0454
xmlui.MetaDataDisplay.field.date: 2012
Language: en (en)
Content Type: Text/Journal Article

Keywords

  • External Memory
  • Master Node
  • Graph Class
  • Internal Memory
  • Real World Graph
Collections
  • PARS-Mitteilungen 2012 [15]

Show full item record


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.

 

 


About uns | FAQ | Help | Imprint | Datenschutz

Gesellschaft für Informatik e.V. (GI), Kontakt: Geschäftsstelle der GI
Diese Digital Library basiert auf DSpace.