Strong Articulation Points and Strong Bridges in Large Scale Graphs

详细信息    查看全文

• 作者：Donatella Firmani ; Loukas Georgiadis ; Giuseppe F. Italiano ; Luigi Laura…
• 关键词：Graph algorithms ; Graph connectivity ; Strong articulation points ; Strong bridges ; Large scale graphs
• 刊名：Algorithmica
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：74
• 期：3
• 页码：1123-1147
• 全文大小：1,249 KB
• 参考文献：1.Aho, A.V., Hopcroft, J.E., Ullman, J.D.: On finding lowest common ancestors in trees. SIAM J. Comput. 5(1), 115–32 (1976)CrossRef MathSciNet MATH
  2.Alstrup, S., Harel, D., Lauridsen, P.W., Thorup, M.: Dominators in linear time. SIAM J. Comput. 28(6), 2117–2132 (1999)CrossRef MathSciNet MATH
  3.Beldiceanu, N., Flener, P., Lorca, X.: The tree constraint. In: Proceedings of the 2nd International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2005), vol. 3524 of LNCS, pp. 64–78. Springer, 30 May–June 1 (2005)
  4.Boldi, P., Vigna, S.: The WebGraph framework I: compression techniques. In: Proceedings of the Thirteenth International World Wide Web Conference (WWW 2004), Manhattan, USA, pp. 595–601. ACM Press (2004)
  5.Buchsbaum, A.L., Georgiadis, L., Kaplan, H., Rogers, A., Tarjan, R.E., Westbrook, J.R.: Linear-time algorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38(4), 1533–1573 (2008)CrossRef MathSciNet MATH
  6.Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.R.: A new, simpler linear-time dominators algorithm. ACM Trans. Program. Lang. Syst. 20(6), 1265–1296 (1998). Corrigendum in 27(3):383–387 (2005)
  7.Cooper, K.D., Harvey, T.J., Kennedy, K.: A simple, fast dominance algorithm. Softw. Pract. Exp. 4, 110 (2001)
  8.Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, London (2009)MATH
  9.Firmani, D., Italiano, G.F., Laura, L., Orlandi, A., Santaroni, F.: Computing strong articulation points and strong bridges in large scale graphs. In: Proceedings of the 11th International Symposium on Experimental Algorithms (SEA), pp. 195–207 (2012)
  10.Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30(2), 209–221 (1985)CrossRef MathSciNet MATH
  11.Georgiadis, L.: Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs. In: ICALP 10: Proceedings of the 37th International Colloquium on Automata, Languages and Programming, pp. 433–442 (2010)
  12.Georgiadis, L., Laura, L., Parotsidis, N., Tarjan, R.E.: Dominator certification and independent spanning trees: an experimental study. In: Proceedings of the 12th International Symposium on Experimental Algorithms (SEA), pp. 284–295. Springer (2013)
  13.Georgiadis, L., Laura, L., Parotsidis, N., Tarjan, R.E.: Loop nesting forests, dominators, and applications. In: Proceedings of the 13th International Symposium on Experimental Algorithms (SEA), pp. 174–186. Springer (2014)
  14.Georgiadis, L., Tarjan, R.E.: Finding dominators revisited. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, pp. 862–871 (2004)
  15.Georgiadis, L., Tarjan, R.E.: Dominator tree verification and vertex-disjoint paths. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 433–442 (2005)
  16.Georgiadis, L., Tarjan, R.E.: Dominators, directed bipolar orders, and independent spanning trees. In: Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 375–386. Springer (2012)
  17.Georgiadis, L., Tarjan, R.E., Werneck, R.F.F.: Finding dominators in practice. J. Graph Algorithms Appl. 10(1), 69–94 (2006)CrossRef MathSciNet MATH
  18.Italiano, G.F., Laura, L., Santaroni, F.: Finding strong bridges and strong articulation points in linear time. Theor. Comput. Sci. 447, 74–84 (2012)CrossRef MathSciNet MATH
  19.Lengauer, T., Tarjan, R.E.: A fast algorithm for finding dominators in a flowgraph. ACM Trans. Program. Lang. Syst. 1(1), 121–141 (1979)CrossRef MATH
  20.Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and analysis of online social networks. In: Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement, IMC’07, New York, NY, USA, pp. 29–42. ACM (2007)
  21.SNAP: Stanford Network Analysis Project. http://​snap.​stanford.​edu/​
  22.Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146–59 (1972)CrossRef MathSciNet MATH
  23.Tarjan, R.E.: Edge-Disjoint Spanning Trees, Dominators, and Depth-First Search. Technical report, Stanford University, Stanford, CA (1974)
  24.Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215–225 (1975)CrossRef MathSciNet MATH
  25.Tarjan, R.E.: Edge-disjoint spanning trees and depth-first search. Acta Inf. 6, 171–185 (1976)CrossRef MathSciNet MATH
  26.Tarjan, R.E.: Applications of path compression on balanced trees. J. ACM 26(4), 690–715 (1979)CrossRef MathSciNet MATH
  27.The WebGraph Framework Home Page. http://​webgraph.​dsi.​unimi.​it/​
  28.Volkmann, L.: Restricted arc-connectivity of digraphs. Inf. Process. Lett. 103(6), 234–239 (2007)CrossRef MATH
  
• 作者单位：Donatella Firmani (1)
  Loukas Georgiadis (2)
  Giuseppe F. Italiano (1)
  Luigi Laura (3)
  Federico Santaroni (1)
  
  1. Department of Civil Engineering and Computer Science Engineering, University of Rome “Tor Vergata”, Rome, Italy
  2. Department of Computer Science and Engineering, University of Ioannina, Ioannina, Greece
  3. Department of Computer, Control, and Management Engineering (DIAG), Research Centre for Transport and Logistic, Sapienza University of Rome, Rome, Italy
  
• 刊物类别：Computer Science
• 刊物主题：Algorithm Analysis and Problem Complexity
  Theory of Computation
  Mathematics of Computing
  Algorithms
  Computer Systems Organization and Communication Networks
  Data Structures, Cryptology and Information Theory
  
• 出版者：Springer New York
• ISSN：1432-0541

文摘

Let \(G=(V,E)\) be a directed graph. A vertex \(v\in V\) (respectively an edge \(e\in 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 fast algorithms for computing all the strong articulation points and all the strong bridges of a directed graph, based on the linear-time algorithms presented in Italiano et al. (Theor Comput Sci 447:74–84, 2012). 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.