Minimum strongly biconnected spanning directed subgraph problem

2022/07/09 by Raed Jaberi, Jaberi, Raed
Computer Science · #Advanced Graph Theory Research #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2207.04321

openalex publication_date 2022/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be a strongly biconnected directed graph. In this paper we consider the problem of computing an edge subset H ⊆ E of minimum size such that the directed subgraph (V,H) is strongly biconnected.

Related

• Minimum 2-edge strongly biconnected spanning directed subgraph problem
• Identifying a 3-vertex strongly biconnected directed subgraph with minimum number of edges
• 2-blocks in strongly biconnected directed graphs
• Approximating the Smallest Spanning Subgraph for 2-Edge-Connectivity in Directed Graphs
• The problem of computing a 2-T-connected spanning subgraph with minimum number of edges in directed graphs