, Performance of linear-time algorithms for the Hamilton instances. Solution qualities (top) and running time in seconds (bottom). Running times and graph sizes (number of edges) are shown in log scale, Figure, vol.4

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network flows: theory, algorithms, and applications, 1993.

S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup, Dominators in linear time, SIAM Journal on Computing, vol.28, issue.6, pp.2117-2149, 1999.

S. Baswana, K. Choudhary, and L. Roditty, Fault tolerant reachability for directed graphs, Distributed Computing, vol.9363, pp.528-543, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01207207

S. Baswana, K. Choudhary, and L. Roditty, Fault tolerant reachability subgraph: Generic and optimal, Proc. 43rd ACM Symp. on Theory of Computing, pp.509-518, 2016.

A. L. Buchsbaum, L. Georgiadis, H. Kaplan, A. Rogers, R. E. Tarjan et al., Lineartime algorithms for dominators and other path-evaluation problems, SIAM Journal on Computing, vol.38, issue.4, pp.1533-1573, 2008.

S. Chechik, T. D. Hansen, G. F. Italiano, V. Loitzenbauer, and N. Parotsidis, Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1900-1918, 2017.

J. Cheriyan and R. Thurimella, Approximating minimum-size k-connected spanning subgraphs via matching, SIAM J. Comput, vol.30, issue.2, pp.528-560, 2000.

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems, vol.13, issue.4, pp.451-490, 1991.

D. Delling, A. V. Goldberg, I. Razenshteyn, and R. F. Werneck, Graph partitioning with natural cuts, 25th International Parallel and Distributed Processing Symposium (IPDPS'11), 2011.

C. Demetrescu, A. V. Goldberg, and D. S. Johnson, 9th DIMACS Implementation Challenge: Shortest Paths, 2007.

J. Edmonds, Edge-disjoint branchings, Combinatorial Algorithms, pp.91-96, 1972.

J. Fakcharoenphol and B. Laekhanukit, An O(log 2 k)-approximation algorithm for the k-vertex connected spanning subgraph problem, Proc. 40th ACM Symp. on Theory of Computing, STOC '08, pp.153-158, 2008.

H. N. Gabow and R. E. Tarjan, Faster scaling algorithms for general graph matching problems, J. ACM, vol.38, pp.815-853, 1991.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979.

N. Garg, V. S. Santosh, and A. Singla, Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp.103-111, 1993.

L. Georgiadis, Testing 2-vertex connectivity and computing pairs of vertex-disjoint s-t paths in digraphs, Proc. 37th Int'l. Coll. on Automata, Languages, and Programming, pp.738-749, 2010.

L. Georgiadis, G. F. Italiano, A. Karanasiou, C. Papadopoulos, and N. Parotsidis, Sparse subgraphs for 2-connectivity in directed graphs, Proc. 15th Int'l. Symp. on Experimental Algorithms, pp.150-166, 2016.

L. Georgiadis, G. F. Italiano, A. Karanasiou, N. Parotsidis, and N. Paudel, Computing 2-connected components and maximal 2-connected subgraphs in directed graphs: An experimental study, Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX), pp.169-183, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01925963

L. Georgiadis, G. F. Italiano, C. Papadopoulos, and N. Parotsidis, Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs, Proc. 23rd European Symposium on Algorithms, pp.582-594, 2015.

L. Georgiadis and R. E. Tarjan, Dominator tree certification and divergent spanning trees, ACM Transactions on Algorithms, vol.12, issue.1, 2015.

L. Georgiadis and R. E. Tarjan, Addendum to "Dominator tree certification and divergent spanning trees, ACM Transactions on Algorithms, vol.12, issue.4, pp.1-56, 2016.

L. Georgiadis, R. E. Tarjan, and R. F. Werneck, Finding dominators in practice, Journal of Graph Algorithms and Applications (JGAA), vol.10, issue.1, pp.69-94, 2006.

A. V. Goldberg and R. E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM, vol.35, pp.921-940, 1988.

J. E. Hopcroft and R. M. Karp, An n 5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, vol.2, pp.225-231, 1973.

G. F. Italiano, L. Laura, and F. Santaroni, Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science, vol.447, pp.74-84, 2012.

S. Khuller, B. Raghavachari, and N. E. Young, Approximating the minimum equivalent digraph, SIAM J. Comput, vol.24, issue.4, pp.177-186, 1995.

G. Kortsarz and Z. Nutov, Approximating minimum cost connectivity problems. Approximation Algorithms and Metaheuristics, 2007.

T. Lengauer and R. E. Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems, vol.1, issue.1, pp.121-162, 1979.

J. Leskovec and A. Krevl, SNAP Datasets: Stanford large network dataset collection, 2014.

W. Mader, Minimal n-fach zusammenhängende digraphen, Journal of Combinatorial Theory, Series B, vol.38, issue.2, pp.102-117, 1985.

D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, vol.26, pp.362-391, 1983.

R. E. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972.

T. Tholey, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Theoretical Computer Science, vol.465, pp.35-48, 2012.

J. Zhao and S. Zdancewic, Mechanized verification of computing dominators for formalizing compilers, Proc. 2nd International Conference on Certified Programs and Proofs, pp.27-42, 2012.

L. Zhao, H. Nagamochi, and T. Ibaraki, A linear time 5/3-approximation for the minimum stronglyconnected spanning subgraph problem, Information Processing Letters, vol.86, issue.2, pp.63-70, 2003.