An \(O(|V|^2)\) algorithm for single connectedness

DOI10.1016/S0020-0190(99)00135-0zbMath0995.05135MaRDI QIDQ1607003

Samir Khuller

Publication date: 25 July 2002

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

zbMATH Keywords

graph algorithmsingle connectedness

Mathematics Subject Classification ID

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

Related Items (6)

On the Complexity of Singly Connected Vertex Deletion ⋮ Addendum to ``An \(O(|V|^{2})\) algorithm for single connectedness ⋮ Make a graph singly connected by edge orientations ⋮ On the complexity of singly connected vertex deletion ⋮ On testing single connectedness in directed graphs and some related problems ⋮ Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

This page was built for publication: An \(O(|V|^2)\) algorithm for single connectedness