Minimum Dominating Set

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.

.

Relevant Pages

  • Re: Visualization of unmeasurable sets and computability
    ... it does not have to be exact! ... rough approximation of the postivie-measure Cantor set: ... So then a "rough visualization" achieved by spitting out ... Does non-measurability of a set imply that no algorithm can ...
    (sci.math)
  • Re: Visualization of unmeasurable sets and computability
    ... it does not have to be exact! ... rough approximation of the postivie-measure Cantor set: ... screen, yielding a rough visualization. ... So then the question comes out to: can we construct an algorithm ...
    (sci.math)
  • Re: Visualization of unmeasurable sets and computability
    ... it does not have to be exact! ... rough approximation of the postivie-measure Cantor set: ... So then the question comes out to: can we construct an algorithm ... then one could spit the estimated points out on a screen and generate ...
    (sci.math)
  • Re: Coloring a graph with exact N colors
    ... > I'm looking for an algorithm to color a graph with exact N colors, ... > usually N is larger than the chromatic number of the graph. ... > and the number of vertices in each indepedent set shoudl be roughly the ...
    (sci.math)
  • Coloring a graph with exact N colors
    ... I'm looking for an algorithm to color a graph with exact N colors, ... and the number of vertices in each indepedent set shoudl be ...
    (comp.compilers)