, 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
Network flows: theory, algorithms, and applications, 1993. ,
Dominators in linear time, SIAM Journal on Computing, vol.28, issue.6, pp.2117-2149, 1999. ,
Fault tolerant reachability for directed graphs, Distributed Computing, vol.9363, pp.528-543, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01207207
Fault tolerant reachability subgraph: Generic and optimal, Proc. 43rd ACM Symp. on Theory of Computing, pp.509-518, 2016. ,
Lineartime algorithms for dominators and other path-evaluation problems, SIAM Journal on Computing, vol.38, issue.4, pp.1533-1573, 2008. ,
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. ,
Approximating minimum-size k-connected spanning subgraphs via matching, SIAM J. Comput, vol.30, issue.2, pp.528-560, 2000. ,
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. ,
Graph partitioning with natural cuts, 25th International Parallel and Distributed Processing Symposium (IPDPS'11), 2011. ,
, 9th DIMACS Implementation Challenge: Shortest Paths, 2007.
Edge-disjoint branchings, Combinatorial Algorithms, pp.91-96, 1972. ,
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. ,
Faster scaling algorithms for general graph matching problems, J. ACM, vol.38, pp.815-853, 1991. ,
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, pp.103-111, 1993. ,
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. ,
Sparse subgraphs for 2-connectivity in directed graphs, Proc. 15th Int'l. Symp. on Experimental Algorithms, pp.150-166, 2016. ,
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
Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs, Proc. 23rd European Symposium on Algorithms, pp.582-594, 2015. ,
Dominator tree certification and divergent spanning trees, ACM Transactions on Algorithms, vol.12, issue.1, 2015. ,
Addendum to "Dominator tree certification and divergent spanning trees, ACM Transactions on Algorithms, vol.12, issue.4, pp.1-56, 2016. ,
Finding dominators in practice, Journal of Graph Algorithms and Applications (JGAA), vol.10, issue.1, pp.69-94, 2006. ,
A new approach to the maximum-flow problem, Journal of the ACM, vol.35, pp.921-940, 1988. ,
An n 5/2 algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, vol.2, pp.225-231, 1973. ,
Finding strong bridges and strong articulation points in linear time, Theoretical Computer Science, vol.447, pp.74-84, 2012. ,
Approximating the minimum equivalent digraph, SIAM J. Comput, vol.24, issue.4, pp.177-186, 1995. ,
Approximating minimum cost connectivity problems. Approximation Algorithms and Metaheuristics, 2007. ,
A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems, vol.1, issue.1, pp.121-162, 1979. ,
SNAP Datasets: Stanford large network dataset collection, 2014. ,
Minimal n-fach zusammenhängende digraphen, Journal of Combinatorial Theory, Series B, vol.38, issue.2, pp.102-117, 1985. ,
A data structure for dynamic trees, Journal of Computer and System Sciences, vol.26, pp.362-391, 1983. ,
Depth-first search and linear graph algorithms, SIAM Journal on Computing, vol.1, issue.2, pp.146-160, 1972. ,
Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Theoretical Computer Science, vol.465, pp.35-48, 2012. ,
Mechanized verification of computing dominators for formalizing compilers, Proc. 2nd International Conference on Certified Programs and Proofs, pp.27-42, 2012. ,
A linear time 5/3-approximation for the minimum stronglyconnected spanning subgraph problem, Information Processing Letters, vol.86, issue.2, pp.63-70, 2003. ,