Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with eO(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O(n2) time algo- rithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O(m3=2), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time O(m3=2 log n), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O(n2 log n) time.
Chechik, S., Hanseny, T.d., Italiano, G.f., Loitzenbauer, V., & Parotsidis, N. (2017). Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1900-1918). Association for Computing Machinery.
|Autori:||Chechik, S; Hanseny, Td; Italiano, Gf; Loitzenbauer, V; Parotsidis, N|
|Titolo:||Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs|
|Nome del convegno:||28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017|
|Luogo del convegno:||Hotel Porta Fira, esp|
|Anno del convegno:||2017|
|Enti collegati al convegno:||Universitat Politecnica de Catalunya|
|Data di pubblicazione:||2017|
|Settore Scientifico Disciplinare:||Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni|
|Tipologia:||Intervento a convegno|
|Citazione:||Chechik, S., Hanseny, T.d., Italiano, G.f., Loitzenbauer, V., & Parotsidis, N. (2017). Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (pp.1900-1918). Association for Computing Machinery.|
|Appare nelle tipologie:||02 - Intervento a convegno|