Re: [Tcllib-devel] ping gsoc graph work ...

[Michał A. <ant...@gm...>]

As not much time left to midterm-evaluation - another update with some
subprocedures for K Center problem and a little description of the problem.

We are given undirected and completed graph G, where edge weights satisfy
triangle inequality (Metric).

Let the k be positive integer.
Let V be set of nodes and E be set of edges for G.
For any set S, which is a subset of V and node v (v is a element of V), let
connect(v, S) be the min cost of the edge, which connects node v with any
node in S.
The goal is to find such S, that |S| = k, and maxv { connect(v,S) } is as
small as possible.

In other words, we are searching for such subset of V, that it will be made
from k nodes, and the max value of connect function will be as small as
possible.

Generally, how algorithm works:

- first step is to sort edges E = {e1.....em} with their costs in not
decreasing order: cost(e1) <= .... <= cost(em)

- now we construct m graphs Gi like this: Gi = (V, Ei). So, set of nodes
remains the same, but we use only Ei edges.
e.g. E5 = {e1,e2,e3,e4,e5} - procedure createGi

- each graph Gi much be two squared -> Gi^2. Gi^2 is such graph that is has
an edge between nodes u and v, if and only if, the distance between those
nodes (in edges, not weights!) is not greater than 2. In other words, we can
go from u to v using max 2 edges. ---> procedure createTwoSquaredGraph

- for each Gi^2 we seek for maximum independent set Mi. Just to clear:
finding maximal is of course NP hard, we seek for maximum set.

- let the j be the min index, such that |Mj| <= k.

- return Mj.

So this is how it works in general. I think with more code and
updates things will get more clear, but for now just a quick look at what it
is planned to achieve.


Best Regards,
Michal Antoniewski