Incorporating DSUs with Tarjan Vishkin for finding BCCs in graphs

Introduction to Algorithm Engineering Project

• Keval Jain | 2021111030
• Sriteja Pashya | 2021111019

---

• Implemented non-parallel version of Tarjan-Vishkin algorithm: An Efficient Parallel Biconnectivity Algorithm.
• Incorporated DSUs when adding edges to G’.
• Implemented Tarjan's Algorithm.
• Compared performance of both on various types of graphs of various sizes.
• Result: Tarjan-Vishkin with DSUs performances better than Tarjan's on Large Graphs.

Execution

• For each code, run the command g++ -std=c++17 -Ofast filename.cpp -o filename.
• Then run ./filename < input_file > output_file.
• To generate random graphs use randomgraph.cpp and run ./randomgraph > input_file.
• Number of vertices and edges can be changed in the code.

Assumptions

• The graph need not be connected.
• Graph need not be simple.
• Graph doesn't have self-loops.