IJBTT

Survey on 2-connectivity in Directed Graphs

	International Journal of Computer Trends and Technology (IJCTT)
	© 2017 by IJCTT Journal
	Volume-49 Number-2
	Year of Publication : 2017
	Authors : T.Manohar Reddy, Dr.P.Chandra Sekhar

T.Manohar Reddy, Dr.P.Chandra Sekhar "Survey on 2-connectivity in Directed Graphs". International Journal of Computer Trends and Technology (IJCTT) V49(2):130-136, July 2017. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.

Abstract -
In this paper, the Survey of some recent results on graph connectivity problems like 2-vertex connectivity and 2-edge connectivity problems in directed graphs have been discussed. 2-vertex and 2-edge connectivity problems in directed graphs are more difficult than on undirected graphs. By using depth first search 2-edge and 2-vertex connectivity, bridges, articulation points can be computed in linear time for undirected graphs. In the case of a directed graph, the same problems have been much more challenging and required the development of new ideas and techniques.

References
1 Douglas West. Introduction to Graph Theory second edition.
2 K. Menger. ZurAllgemeinekurventheorie. Fund. Math., 10:96–115, 1927.
3 http://www.geeksforgeeks.org/tag/graph-connectivity
4 https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial
5 R. Jaberi. Computing the 2-blocks of directed graphs. RAIRO-Theor. Inf. Appl.,49(2):93119,2015.doi:10.1051/ita/2015001.
6 R. Jaberi. On computing the 2-vertex-connected components of directed graphs.DiscreteApplied Mathematics, 204:164–172,2016. doi:10.1016/j.dam.2015.10.001.
7 T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. ACM Transactions on Programming Languages and Systems, 1(1):121–41, 1979
8 http://www.dcc.fc.up.pt/~acm/PRinv.pdf
9 H. Nagamochi and T.Watanabe. Computing k-edge-connected components of a multigraph.IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,E76–A(4):513–517, 1993
10 G. F. Italiano, L. Laura, F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science. 447 (2012) 74–84.
11 R. Diestel, Graph Theory, 2nd ed., Springer, New York, 2000, pp. 43–44.
12 G. F. Italiano, L. Laura, F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science. 447 (2012) 74–84.
13 R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput.1(2) (1972) 146–160.
14 S. Alstrup, D. Harel, P.W. Lauridsen, M. Thorup, Dominators in linear time.SIAM J. Comput. 28(6) (1999) 2117–2132.
15 A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, J. R.Westbrook, Linear-time algorithms for dominators and other path-evaluationproblems,SIAM J.Comput. 38(4) (2008) 1533–1573.
16 https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4569431/
17 Stoer M. and Wagner F., A simple min-cut algorithm, J. ACM 44(4), 1997. doi: 10.1145/263867.263872
18 Ford L. R. and Fulkerson D. R., Flows in Networks, Princeton University Press Princeton, New Jersey, 1962
19 Goldberg A. V. and Tarjan R. E., A new approach to maximum flow problem, J. ACM 35(4), 1988. doi: 10.1145/48014.61051
20 D. Firmani, G. F. Italiano, L. Laura, A. Orlandi, and F. Santaroni. 2012. Computing strong articulationpoints and strong bridges in large scale graphs. In Proceedings of the 10th International Symposium on Experimental Algorithms. 195–207.
21 W. Fraczak, L. Georgiadis, A. Miller, and R. E. Tarjan. 2013. Finding Dominators via disjoint set union.Journal of Discrete Algorithms 23,DOI:http://dx.doi.org/10.1016/j.jda.2013.10.003
22 A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan, and J. R. Westbrook. 2008. Lineartimealgorithms for dominators and other path-evaluation problems. SIAM J. Comput. 38, 4 (2008)

Keywords
In the case of a directed graph, the same problems have been much more challenging and required the development of new ideas and techniques.