Algorithm for 2-Vertex Connectivity in Directed Graphs

Authors(1) :-T Manohar Reddy

Graph theory is very important in solving many problems efficiently. Each graph is made up of vertices and edges. Common notation used to represent a graph is G = (V, E) where V is a set of vertices and E is a set of edges. The dynamics of graphs were understood and explored well in the literature while there is insufficient research related to directed graphs. There are many problems to be solved with respect to graphs. For instance, 2-vertex connectivity is an important problem to be addressed. Recently Georgiadis et al. focused on this problem and found that two vertices v and w are 2-vertex connected when there are two internally vertex -disjoint paths coming from v to w and two internally vertex disjoint paths from w to v. Many kinds of combinations were explored in their work. However, it is useful to have more investigation on this. In this paper we reviewed directed graphs with 2-vertex connectivity with some algorithms. Our study reviewed that the approaches can be used effectively to solve select problems in the real world.

Authors and Affiliations

T Manohar Reddy
Department of Computer Engineering, JNTU College of Engineering, Anantapur, Andhra Pradesh India

Graph theory, directed graphs, 2-edge connectivity

  1. NilakanthaPaudel, LoukasGeorgiadis and Giuseppe F. Italiano. (2017). Computing Critical Nodes in Directed Graphs. SIAM.á P43-57.
  2. Mohsen Ghaffari and Hsin-HaoSu .Distributed Degree Splitting, Edge Coloring, and Orientations.p2505-2523.
  3. Martin Merker. (2017). Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree. ELSEVIER.122 , P91ľ108.
  4. louisesperet, remi de joannis de verclos, tien-nam le, ' and stephanthomass ' e. (2017). additive bases and flows in graphs, p1-11.
  5. Samuel Fiorini Martin Gro▀JochenKonemann and Laura Sanita .(2017). A 3 2 -Approximation Algorithm for Tree Augmentation via Chvatal-Gomory Cuts, p1-21.
  6. Monika Henzinger , Andrea Lincoln , Stefan Neumann , and Virginia Vassilevska Williams . (2017). Conditional Hardness for Sensitivity Problems, p1-33.
  7. JinghuaHe ,Erling Wei , Dong Ye and ShaohuiZhai. (2017). On Perfect Matchings in Matching Covered Graphs, p1-10.
  8. Gregory Gutin , M. S. Ramanujan , Felix Reidl and Magnus Wahlstrom. (2017). Path-contractions, edge deletions and connectivity preservation, p1-10.
  9. LoukasGeorgiadis,ThomasDueholmHansen,Giuseppe F. Italiano,SebastianKrinninger and Nikos Parotsidis. (2017). Decremental Data Structures for Connectivity and Dominators in Directed Graphs, p1-39.
  10. SurenderBaswanaAyushGoel and Shahbaz Khan. (2017). Incremental DFS algorithms: a theoretical and experimental study, p1-31.
  11. Gaborhorvath, chrystopher l. nehaniv, and karolypodoski. (2017). the maximal subgroups and the complexity of the flow semigroup of finite (di)graphs, p1-23.
  12. WeijuanZhang ,JianguoQian and Fuji Zhang. (2017). Flip-distance between ?-orientations of graphs embedded on plane and sphere, p1-15
  13. Dan Archdeacon,MattDeVos,StefanHannie and BojanMohar. (2017). Whitney's Theorem for 2-Regular Planar Digraphs, p1-8.
  14. Jacob Holm, Giuseppe F. Italiano , Adam Karczmarz , Jakub??cki, Eva Rotenberg , and PiotrSankowski. (2017). Contracting a Planar Graph Efficiently, p1-21.
  15. LoukasGeorgiadis, Giuseppe F. Italiano, Luigi Laura,NikosParotsidis. (2017). 2-Edge Connectivity in Directed Graphs. SIAM, p1988-2005.
  16. R. E. Tarjan. Depth-_rst search and linear graph algorithms. SIAM Journal on Computing, 1(2):146_160, 1972.
  17. L. Georgiadis, G. F. Italiano, L. Laura, and N. Parotsidis.2-vertex connectivity in directed graphs.In Proceedings of the 42th International Colloquium on automata, Languages, and Programming, 2015.

Publication Details

Published in : Volume 2 | Issue 4 | July-August 2017
Date of Publication : 2017-09-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 875-879
Manuscript Number : CSEIT1172492
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

T Manohar Reddy, "Algorithm for 2-Vertex Connectivity in Directed Graphs ", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 2, Issue 4, pp.875-879, July-August-2017.
Journal URL :

Article Preview

Follow Us

Contact Us