Minimum 2-vertex-twinless connected spanning subgraph problem

2020/01/11 by Raed Jaberi, Jaberi, Raed
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2001.03788

openalex publication_date 2020/01/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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¹ 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¹.

Related

• The problem of computing a 2-T-connected spanning subgraph with minimum number of edges in directed graphs
• An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-free Two-Edge-Cover
• A Unified Approach for Approximating 2-Edge-Connected Spanning Subgraph and 2-Vertex-Connected Spanning Subgraph
• Twinless articulation points and some related problems
• A 17/12-Approximation Algorithm for 2-Vertex-Connected Spanning Subgraphs on Graphs with Minimum Degree At Least 3