We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of a 2-vertex connected directed graph, and provide new efficient algorithms. We provide two linear-time algorithms, the first based on a linear-time test for 2-vertex connectivity and divergent spanning trees, and the second based on low-high orders, that correspondingly give 3- and 2-approximations. Then we show that these linear-time algorithms can be combined with an algorithm of Cheriyan and Thurimella that achieves a 3/2-approximation. The combined algorithms preserve the 3/2 approximation guarantee of the Cheriyan-Thurimella algorithm and improve its running time from O(m2) to O(mn+n2), for a digraph with n vertices and m edges. Finally, we present an experimental evaluation of the above algorithms for a variety of input data. The experimental results show that our linear-time algorithms perform very well in practice. Furthermore, the experiments show that the combined algorithms not only improve the running time of the Cheriyan-Thurimella algorithm, but it may also compute a better solution.

Approximating the smallest 2-vertex connected spanning subgraph of a directed graph / Georgiadis, L.; Italiano, Giuseppe Francesco; Karanasiou, A.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 807:(2020), pp. 185-200. [10.1016/j.tcs.2019.09.040]

Approximating the smallest 2-vertex connected spanning subgraph of a directed graph

Italiano G. F.;
2020

Abstract

We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of a 2-vertex connected directed graph, and provide new efficient algorithms. We provide two linear-time algorithms, the first based on a linear-time test for 2-vertex connectivity and divergent spanning trees, and the second based on low-high orders, that correspondingly give 3- and 2-approximations. Then we show that these linear-time algorithms can be combined with an algorithm of Cheriyan and Thurimella that achieves a 3/2-approximation. The combined algorithms preserve the 3/2 approximation guarantee of the Cheriyan-Thurimella algorithm and improve its running time from O(m2) to O(mn+n2), for a digraph with n vertices and m edges. Finally, we present an experimental evaluation of the above algorithms for a variety of input data. The experimental results show that our linear-time algorithms perform very well in practice. Furthermore, the experiments show that the combined algorithms not only improve the running time of the Cheriyan-Thurimella algorithm, but it may also compute a better solution.
2020
2-Vertex-connected spanning subgraphs, Approximation algorithms, Directed graphs, Experimental evaluation of algorithms, Vertex connectivity
Approximating the smallest 2-vertex connected spanning subgraph of a directed graph / Georgiadis, L.; Italiano, Giuseppe Francesco; Karanasiou, A.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 807:(2020), pp. 185-200. [10.1016/j.tcs.2019.09.040]
File in questo prodotto:
File Dimensione Formato  
Italiano_Approximating the smallest 2-vertex_2020.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 5.99 MB
Formato Adobe PDF
5.99 MB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

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/11385/192105
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
  • OpenAlex ND
social impact