Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs

DOI10.1137/1.9781611974782.124zbMath1410.05196arXiv1705.10709OpenAlexW2955681777MaRDI QIDQ4575870

Giuseppe F. Italiano, Veronika Loitzenbauer, Thomas Dueholm Hansen, Shiri Chechik, Nikos Parotsidis

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (6)

Sparse certificates for 2-connectivity in directed graphs ⋮ Strong Connectivity in Directed Graphs under Failures, with Applications ⋮ Unnamed Item ⋮ Finding densest \(k\)-connected subgraphs ⋮ Approximating the smallest 2-vertex connected spanning subgraph of a directed graph ⋮ Contracting a Planar Graph Efficiently

This page was built for publication: Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs