Computing 2-Connected Components and Maximal 2-Connected Subgraphs in Directed Graphs: An Experimental Study
Loukas Georgiadis, Giuseppe Francesco Italiano, Aikaterini Karanasiou, Nikos Parotsidis, Nilakantha Paudel · Society for Industrial and Applied Mathematics eBooks · 2018
Motivated by very recent work on 2-connectivity in directed graphs, we revisit the problem of computing the 2-edge- and 2-vertex-connected components, and the maximal 2-edge- and 2-vertex-connected subgraphs of a directed graph G. We explore the design space for efficient algorithms in practice, based on recently proposed techniques, and conduct a thorough empirical study to highlight the merits and weaknesses of each technique.