Minimum 2-vertex-twinless connected spanning subgraph problem

01/11/2020

∙

by   Raed Jaberi, et al.

∙

0

∙

share

Given a 2-vertex-twinless connected directed graph G=(V,E), the minimum 2-vertex-twinless connected spanning subgraph problem is to find a minimum cardinality edge subset E^t⊆ E such that the subgraph (V,E^t) is 2-vertex-twinless connected. Let G^1 be a minimal 2-vertex-connected subgraph of G. In this paper we present a (2+a_t/2)-approximation algorithm for the minimum 2-vertex-twinless connected spanning subgraph problem, where a_t is the number of twinless articulation points in G^1.