Skip to content

Latest commit

 

History

History
44 lines (32 loc) · 2.17 KB

README.md

File metadata and controls

44 lines (32 loc) · 2.17 KB
Raw

Triconnectivity

License: MIT Code Style: black License: MIT License: MIT

A set of generic implementations for finding $3$-edge-connected and $3$-vertex-connected components in a graph (implemented in Python). Made for junior-year independent work for Princeton University's COS Department.

Abstract

This paper explores the implementation and application of a well known $3$-edge-connectivity algorithm. We use Tsin's algorithm to analyze, in linear time, the connectivity of essential networks [1]. This includes state-wide road networks, distributed systems, and even the structure of the Internet. Implementations and applications of $3$-edge-connectivity are relatively unexplored, and this paper aims to fill a gap in the surrounding academic literature through rigorous explanation and demonstration.

Requirements

  • Python 3.9 (download) or PyPy (download)
  • pipenv (call pip install pipenv globally)

Setup

  1. Ensure requirements are installed correctly.
  2. Navigate to project folder.
  3. Call pipenv install to install required pip packages into the virtual environment.
  4. Prosper.

📝 License

Copyright © 2023 Mike Scornavacca.
This project is MIT licensed.

References

[1] Y. H. Tsin, “A Simple 3-Edge-Connected Component Algorithm,” Theory Comput Syst, vol. 40, no. 2, pp. 125–142, Feb. 2007, doi: 10.1007/s00224-005-1269-4.