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.

Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs

Italiano, Giuseppe F.;
2017-01-01

Abstract

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.
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Hotel Porta Fira, esp
2017
Universitat Politecnica de Catalunya
Rilevanza internazionale
2017
Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI
English
Software; Mathematics (all)
Intervento a convegno
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.
Chechik, S; Hanseny, Td; Italiano, Gf; Loitzenbauer, V; Parotsidis, N
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/201128
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 7
social impact