Re: Minimum Spanning Tree on a Grid of Points

"Gerry Myerson" <gerry@xxxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:gerry-72E535.13111622052006@xxxxxxxxxxxxxxxxxxxxx
In article <e4ncn4$s9c$1@xxxxxxxxxxxxxxxxxxxx>,
"Alun Harford" <usenet@xxxxxxxxxxxxxxxxx> wrote:

<C6L1V@xxxxxxx> wrote in message
news:1148138537.873812.96440@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Alun Harford wrote:
I want to find the minimum spanning tree of a grid of n*n points.
And an n*m grid.

While finding minimum spanning trees in the general case is NP
complete,

There are fast algorithms to determine minimum spanning trees in
polynomial time. See, eg., Kruskal's Algoirthm, or Prim's Algorithm.
Maybe your meaning of the term minimum spanning tree is different from
the standard?

Yes, sorry. I'll try again:

While finding the Steiner tree in the general case in NP complete...

This might be worth a look:

MR1369336 (96i:90070)
Harris, Frederick C., Jr.(1-NV-C)
An introduction to Steiner minimal trees on grids. (English. English
summary)
Proceedings of the Twenty-sixth Southeastern International Conference on
Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995).
Congr. Numer. 111 (1995), 3--17.
90C35 (05C05 05C35)

It's excellent.
Thanks for the reference.

Alun Harford


.