# Linear Sphericity Testing of 3-Connected Single Source Digraphs

Document Type : Research Paper

Author

Abstract

It has been proved that sphericity testing for digraphs is an
NP-complete problem. Here, we
investigate sphericity of 3-connected single source digraphs. We
provide a new combinatorial characterization of sphericity and give
a linear time algorithm for sphericity testing. Our algorithm tests
whether a 3-connected single source digraph with $n$ vertices is
spherical in $O(n)$ time.

Keywords

### History

• Receive Date: 31 May 2009
• Revise Date: 17 March 2012
• Accept Date: 23 March 2010