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

DOI10.1016/S0020-0190(99)00135-0zbMATH Open0995.05135MaRDI QIDQ1607003FDOQ1607003

Authors: Samir Khuller 

Publication date: 25 July 2002

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

Recommendations

• On testing single connectedness in directed graphs and some related problems
• Determining uni-connectivity in directed graphs
• Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity
• A simple test on 2-vertex- and 2-edge-connectivity
• A linear algorithm of checking of the graph connectness

zbMATH Keywords

graph algorithmsingle connectedness

Mathematics Subject Classification ID

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

Cited In (8)

• An O (log( n ) ^4/3 ) space algorithm for ( s, t ) connectivity in undirected graphs
• Comparative study and proof of single-pass connected components algorithms
• 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

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