Hallo there,
me and my friends are implementing a fixed-parameter algorithm for the
3-HS problem described in http://tinyurl.com/9mdnqj
This problem can be seen as vertex cover on hypergraphs. So here's an
example:
Vertices: {x,y,z,s,t}
Hyperedges: {{x,y,z},{z,t,x},{s,t,y},{t,s}}
One minimum Set of vertices, covering all the edge would be: {t,y}
.......................................................................................................................
Now my problem:
One important concept of the above algorithm is "domination". A Vertex
A is dominating another vertex B, if every edge with B, also has A in
it. => B isn't in any edge without A.
How can i efficiently calculate that?
(The data structure is no limitation, because it will be designed
especially for this problem.)
With hashsets / table-based algorithms, i think, it's possible to
calculate all dominating sets in O(V*E) from scratch. Is there
anything better? (The only thing i see, is that O(V+E) has to be the
minimum Complexity)
An alternative would be calculating the domination for one node only
and update special informations in the data structure, so that
calculation is only necessary with changed things in this
informations. (after adding, removing edges)
But what to save for speeding up the calculation?
- a container of neighbor nodes (all nodes which occure together in
"any" set) ? Doesn't seem to help.
Ah, one more thing: If this is a common problem with lots of
information in the internet, then a keyword should be enough. But i
didn't find anything about it. Hard to describe the problem without
intefering with the "dominating-set-problem" :-)
Thanks for all your ideas
Sascha
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
