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

DOI10.1016/S0020-0190(99)00135-0MaRDI QIDQ1607003zbMATH OpenFDO

Authors 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

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

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

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)