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


Volume 37, No. 3
September 2011
Pages 291-304
  • Receive Date: 31 May 2009
  • Revise Date: 17 March 2012
  • Accept Date: 23 March 2010
  • First Publish Date: 15 March 2011