Finding thek smallest spanning trees |
| |
Authors: | David Eppstein |
| |
Institution: | (1) Department of Information and Computer Science, University of California, 92717 Irvine, CA, USA |
| |
Abstract: | We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k
2); for planar graphs this bound can be improved toO(n+k
2). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k
2
n+n logn,k
2+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k
2). |
| |
Keywords: | F 1 3 F 2 2 G 2 2 I 2 8 |
本文献已被 SpringerLink 等数据库收录! |
|