Abstract
B. Szymanski and S. Koenig. The Complexity of Node Counting on Undirected Graphs. Technical Report College of Computing, Georgia Institute of Technology, Atlanta (Georgia), 1999.Abstract: We analyze the complexity of Node Counting, a graph-traversal method. We show that the complexity of Node Counting on undirected graphs is Ω(nsqrt((1/6-ε) n)), where 0 < ε < 1/6 is an arbitrarily small constant and n is the number of vertices.
Download the paper in gzipped postscript (large download time).
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.