Prev: Seminar by Prof Mike Holcombe, 10 March 2009: Formal methods, supercomputers and simulation - understanding complex biological, economic and social systems
Next: Call for papers: TMFCS-10, USA, July 2010
From: anwo on 6 Mar 2010 07:36
First of all: I only know some graph theory basics (with terms in
German), so I'm not sure if all of the following will make sense to
the reader ...

This is a real problem converted into a graph theory problem.

Given:
a simple undirected graph without isolated vertexes
G = (V, E)

Wanted:
a set of cliques (complete graphs)
{K_1, K_2, ..., K_n}
where
K_i = (V_i, E_i), i = 1..n
and
union(V_i) = V i = 1..n
union(E_i) = E i = 1..n

what I want this to mean:
- the union of cliques must cover the original graph exactly,
overlapping cliques are allowed
- the notation does not yet specify the number of vertexes for each
clique (of course!), if needed I will use K^1, K^2, ... for that

Optimization goal: either
(1) n -> min
or
(2) sum( |V_i| ) -> min (minimize the overall number of vertexes
used for the cliques)

not sure about that, maybe both goals are identical? If not, then I
will prefer whatever is simpler to calculate.

There is a trivial solution where each clique is a K^2, but the
resulting amount of data is unnecessarily large. Anything better will
help.

For |V| (= the number of vertexes), I expect quite a big number, so
the algorithm needs to be fast, but does not need to give exact
results (determining cliques is NP-hard or something?); I'm probably
looking for some kind of approximation.

I'm not in a hurry with this, useful replies are welcome at any
time ...
 | 
Pages: 1
Prev: Seminar by Prof Mike Holcombe, 10 March 2009: Formal methods, supercomputers and simulation - understanding complex biological, economic and social systems
Next: Call for papers: TMFCS-10, USA, July 2010