Addendum to ``An O(|V|^2) algorithm for single connectedness

DOI10.1016/S0020-0190(00)00054-5zbMATH Open1339.05391OpenAlexW24382917MaRDI QIDQ294778FDOQ294778

Authors: Samir Khuller 

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000000545?np=y

Recommendations

• An \(O(|V|^2)\) algorithm for single connectedness
• scientific article; zbMATH DE number 437577
• A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
• On testing single connectedness in directed graphs and some related problems
• A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• Augmenting Undirected Edge Connectivity in Õ(n2) Time
• A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
• scientific article; zbMATH DE number 1303592
• On the Complexity of Singly Connected Vertex Deletion
• On the complexity of singly connected vertex deletion

Mathematics Subject Classification ID

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

Cites Work

• Determining uni-connectivity in directed graphs
• An \(O(|V|^2)\) algorithm for single connectedness

Cited In (3)

• On the Complexity of Singly Connected Vertex Deletion
• On the complexity of singly connected vertex deletion
• On testing single connectedness in directed graphs and some related problems

This page was built for publication: Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness

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