TY - JOUR
ID - 366
TI - Linear Sphericity Testing of 3-Connected Single Source Digraphs
JO - Bulletin of the Iranian Mathematical Society
JA - BIMS
LA - en
SN - 1017-060X
AU - Dolati, A.
AD -
Y1 - 2011
PY - 2011
VL - 37
IS - No. 3
SP - 291
EP - 304
KW - Embedding
KW - upward embedding
KW - sphericity
KW - single
source digraph
DO -
N2 - 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.
UR - http://bims.iranjournals.ir/article_366.html
L1 - http://bims.iranjournals.ir/article_366_32f7b095391488c7c2d848a209f52492.pdf
ER -