Minimum 2-vertex strongly biconnected spanning directed subgraph problem

DOI10.47443/DML.2021.0024MaRDI QIDQ5051435zbMATH OpenOpenAlexFDO

Authors Raed Jaberi

Publication date 23 November 2022

Published in Discrete Mathematics Letters (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2008.00496

zbMATH Keywords

approximation algorithmsgraph algorithmsdirected graphsstrongly connected graphsstrongly biconnected directed graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Recommendations

• Approximating the smallest spanning subgraph for 2-edge-connectivity in directed graphs
• Computing the 2-blocks of directed graphs
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• How to make a strongly connected digraph two-connected
• 2-edge connectivity in directed graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 7765396 (Why is no real title available?)
• 2-edge-twinless blocks
• A simple test on 2-vertex- and 2-edge-connectivity
• Approximating Minimum-Size k-Connected Spanning Subgraphs via Matching
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Approximating the smallest 2-vertex connected spanning subgraph of a directed graph
• Computing 2-twinless blocks
• Depth-First Search and Linear Graph Algorithms
• Dominator tree certification and divergent spanning trees
• Ecken vom Grad n in minimalen n-fach zusammenhängenden Graphen
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• Finding strong bridges and strong articulation points in linear time
• Minimal n-fach zusammenhängende Digraphen. (Minimally n-connected digraphs)
• Minimale \(n\)-fach kantenzusammenhängende Graphen
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs

Cited in

(1)

• The minimum spanning strong subdigraph problem is fixed parameter tractable

This page was built for publication: Minimum 2-vertex strongly biconnected spanning directed subgraph problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5051435)