The Complexity of Node Counting on Undirected Graphs
Boleslaw Karol Szymanski, Sven Koenig · 1998
We analyze the complexity of Node Counting, a graph-traversal method. We show that the complexity of Node Counting on undirected graphs is, where fffiffifl "! is an arbitrarily small constant and is the number of vertices. 1