2026-07-20T07:32:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7629 2024-03-12T11:58:37Z ddc:004 open_access

Approximating the Smallest 2-Vertex-Connected Spanning Subgraph via Low-High Orders Georgiadis, Loukas Italiano, Giuseppe F. Karanasiou, Aikaterini 2-vertex connectivity approximation algorithms directed graphs Let G = (V, E) be a 2-vertex-connected directed graph with m edges and n vertices. We consider the problem of approximating the smallest 2-vertex connected spanning subgraph (2VCSS) of G, and provide new efficient algorithms for this problem based on a clever use of low-high orders. The best previously known algorithms were able to compute a 3/2-approximation in O(m n+n 2) time, or a 3-approximation faster in linear time. In this paper, we present a linear-time algorithm that achieves a better approximation ratio of 2, and another algorithm that matches the previous 3/2-approximation in O(m n + n 2 ) time. We conducted a thorough experimental evaluation of all the above algorithms on a variety of input graphs. The experimental results show that both our two new algorithms perform well in practice. In particular, in our experiments the new 3/2-approximation algorithm was always faster than the previous 3/2-approximation algorithm, while their two approximation ratios were close. On the other side, our new linear-time algorithm yielded consistently better approximation ratios than the previously known linear-time algorithm, at the price of a small overhead in the running time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Loukas Georgiadis and Giuseppe F. Italiano and Aikaterini Karanasiou 2017 Is Part Of LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2017.9 urn:nbn:de:0030-drops-76299 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.9 eng https://creativecommons.org/licenses/by/3.0/legalcode