Computing Strong Articulation Points and Strong Bridges in Large Scale Graphs

详细信息    查看全文

• 作者：Donatella Firmani (1) firmani@dis.uniroma1.it
  Giuseppe F. Italiano (2) italiano@disp.uniroma2.it
  Luigi Laura (1) laura@dis.uniroma1.it
  Alessio Orlandi (3) aorlandi@di.unipi.it
  Federico Santaroni (2) santaroni@disp.uniroma2.it
• 关键词：graph algorithms – ; strong connectivity – ; strong articulation points – ; strong bridges – ; large scale graphs
• 刊名：Lecture Notes in Computer Science
• 出版年：2012
• 出版时间：2012
• 年：2012
• 卷：7276
• 期：1
• 页码：195-207
• 全文大小：288.5 KB
• 参考文献：1. Alstrup, S., Harel, D., Lauridsen, P.W., Thorup, M.: Dominators in linear time. SIAM J. Comput. 28(6), 2117–2132 (1999)
  2. Beldiceanu, N., Flener, P., Lorca, X.: The tree Constraint. In: Bart谩k, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, pp. 64–78. Springer, Heidelberg (2005)
  3. Boldi, P., Vigna, S.: The WebGraph framework I: Compression techniques. In: Proc. 13th Int. World Wide Web Conference (WWW 2004), pp. 595–601 (2004)
  4. Broder, A.Z., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.L.: Graph structure in the web. Computer Networks 33(1-6), 309–320 (2000)
  5. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009)
  6. Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. Journal of Computer and System Sciences 30(2), 209–221 (1985)
  7. Georgiadis, L.: Testing 2-Vertex Connectivity and Computing Pairs of Vertex-Disjoint s-t Paths in Digraphs. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 738–749. Springer, Heidelberg (2010)
  8. Georgiadis, L., Tarjan, R.E., Werneck, R.F.F.: Finding dominators in practice. J. Graph Algorithms Appl. 10(1), 69–94 (2006)
  9. Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theoretical Computer Science (to appear), doi: http://dx.doi.org/10.1016/j.tcs.2011.11.011
  10. Lengauer, T., Tarjan, R.E.: A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1(1), 121–141 (1979)
  11. Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proc. 7th ACM SIGCOMM Conference on Internet Measurement, IMC 2007, pp. 29–42 (2007)
  12. SNAP: Stanford Network Analysis Project, http://snap.stanford.edu/
  13. Tarjan, R.E.: Edge-disjoint spanning trees, dominators, and depth-first search. Technical report, Stanford, CA, USA (1974)
  14. Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Inf. 6, 171–185 (1976)
  15. Volkmann, L.: Restricted arc-connectivity of digraphs. Inf. Process. Lett. 103(6), 234–239 (2007)
  16. The WebGraph Framework Home Page, http://webgraph.dsi.unimi.it/
• 作者单位：1. Dept. of Computer Science and Systems, Sapienza Univ. of Rome, via Ariosto, 25, 00185 Roma, Italy2. Dept. of Computer Science, Systems and Production, Univ. of Rome 鈥淭or Vergata鈥? via del Politecnico 1, 00133 Roma, Italy3. Dept. of Computer Science, Univ. of Pisa, Largo Bruno Pontecorvo 3, 56127 Pisa, Italy
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Let G = (V,E) be a directed graph. A vertex v ∈ V (respectively an edge e ∈ E) is a strong articulation point (respectively a strong bridge) if its removal increases the number of strongly connected components of G. We implement and engineer the linear-time algorithms in [9] for computing all the strong articulation points and all the strong bridges of a directed graph. Our implementations are tested against real-world graphs taken from several application domains, including social networks, communication graphs, web graphs, peer2peer networks and product co-purchase graphs. The algorithms implemented turn out to be very efficient in practice, and are able to run on large scale graphs, i.e., on graphs with ten million vertices and half billion edges. Our experiments on such graphs highlight some properties of strong articulation points, which might be of independent interest.