Re: Minimum Dominating Set

Luis Quesada a écrit :
Sadeq wrote:

Hi all,

Is there an algorithm for finding Minimum Dominating Set of a graph?
This algorithm should find the exact answer, not the approximation one.
Also, it shouldn't use brute force (trying all possible cases) to find
the answer, but it can be of any complexity.

Thanks in advance.


Have you had a look at:

A Note on the Complexity of Minimum Dominating Set. F. Grandoni. Journal of Discrete Algorithms. (To appear)

http://www.dsi.uniroma1.it/~grandoni/Gjda.pdf

?

Grandoni suggests an algorithm for solving this problem whose complexity is O(1.81^n).

Luis

Hi,

In the article "Measure and conquer: Domination - A case study",
(proceedings of ICALP 2005, Springer-Verlag, LNCS 3380, pp. 192-203)
the authors (Fomin, Kratsch and Grandoni) proved that this algorithm has running time O(1.5263^n) (and polynomial space) or O(1.5137^n) (and exponential space).

Mathieu
.

Relevant Pages

  • Re: Minimum Dominating Set
    ... Is there an algorithm for finding Minimum Dominating Set of a graph? ... This algorithm should find the exact answer, ... A Note on the Complexity of Minimum Dominating Set. ... Grandoni suggests an algorithm for solving this problem whose complexity is O. ...
    (comp.theory)
  • Re: FUD about CGD and GBDE
    ... >government has approved the use of AES with 256 bit keys for very ... that stress on the algorithm and maintain 256 bits of margin. ... I don't seriously think that either of CGD or GBDE will be broken ... The first reason is that it adds complexity. ...
    (freebsd-hackers)
  • Re: Hooray: the Church of Scotland shows the way
    ... If you are simply pointing out the limitations of algorithmic machines then I agree completely. ... any Turing machine could print out the solution to a non-computable problem if that solution were part of the machine's algorithm. ... Given the complexity of the universe it doesn't seem unlikely that the solutions to all manner of non-computable problems have been physically realised in some form and lie there waiting for us to latch on to them somehow. ... Whilst it's true that fundamental physics are essentially algorithmic in nature, ...
    (uk.religion.christian)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ... cannot be algorithmically random. ...
    (talk.origins)
  • Re: Intro to Programming w/ Machine Language
    ... > Based upon your previous posts, I found this pretty surprising. ... > If n is sufficiently large, the Ocomplexity obviously matters. ... where's the Oor Oalgorithm that's ... people use in the good old "assembly vs. HLL" religous wars. ...
    (alt.lang.asm)