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