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

DOI10.1016/S0020-0190(00)00054-5MaRDI QIDQ294778zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cites work

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

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)