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
A. Dolati, "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.
