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.
Dolati, A. (2011). Linear Sphericity Testing of 3-Connected Single Source Digraphs. Bulletin of the Iranian Mathematical Society, 37(No. 3), 291–304.
MLA
Dolati, A. "Linear Sphericity Testing of 3-Connected Single Source Digraphs", Bulletin of the Iranian Mathematical Society, 37, No. 3, 2011, 291–304.
HARVARD
Dolati, A. (2011). 'Linear Sphericity Testing of 3-Connected Single Source Digraphs', Bulletin of the Iranian Mathematical Society, 37(No. 3), pp. 291–304.
CHICAGO
Dolati, A., "Linear Sphericity Testing of 3-Connected Single Source Digraphs." Bulletin of the Iranian Mathematical Society, 37 No. 3 (2011): 291–304,
VANCOUVER
Dolati A. Linear Sphericity Testing of 3-Connected Single Source Digraphs. BIMS. 2011;37(No. 3):291–304.
