Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: an experimental study. (English) Zbl 1430.68210
Pagh, Rasmus (ed.) et al., Proceedings of the 20th workshop on algorithm engineering and experiments, ALENEX ’18, New Orleans, LA, January 7–8, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). 169-183 (2018).
Summary: 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.
For the entire collection see [Zbl 1380.68013].
For the entire collection see [Zbl 1380.68013].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C40 | Connectivity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W05 | Nonnumerical algorithms |
