Re: Complexity of graph problems

Michael Schnupp <michas@xxxxxxxxxxxxxx> once said:
> Hi,
>
> I'm working on a project on the computational complexity of some
> special graph problems.
>
> I wonder if there is an overview showing which standard problems
> an NP-hard on which graph classes. (Ideally with an pointer to the proof.)
>

Can anyone give me some information on the general complexity of finding the
dominating set of a graph?

Thanks in advance,
NG
--
"The life of a repoman is always intense."
.

Relevant Pages

  • Re: Complexity of graph problems
    ... >> I'm working on a project on the computational complexity of some ... >> special graph problems. ... >> an NP-hard on which graph classes. ... It is NP-complete. ...
    (comp.theory)
  • Complexity of graph problems
    ... I'm working on a project on the computational complexity of some ... special graph problems. ... an NP-hard on which graph classes. ... Is vertex-cover on chordal graphs still NP-complete? ...
    (comp.theory)
  • Re: Its Not Our Fault
    ... Didja ever notice the global warmers always use the SAME little graph, ... of films from across the planet. ... WHOLE graph, made by core sampling oceanographers, geologists, etc., back ... showing totally different flora and fauna at each level. ...
    (rec.boats)
  • Re: Create a line graph of quanitity of values
    ... I am using excel to create a graph showing the ages of my employees. ... quantity of employees on the Y axis and the age ranges on the X axis. ...
    (microsoft.public.excel.charting)
  • Graph of 205 craps decisions
    ... Here are two links to the two graph pages ... showing the plotting of 205 craps decisions. ... Each table, each player, each session or group of sessions will have ... different patterns. ...
    (rec.gambling.craps)