Re: Complexity of graph problems
- From: Jaisingh Solanki <jai@xxxxxxxxxxxxxxxxxx>
- Date: Fri, 25 Nov 2005 04:28:17 +0000 (UTC)
Nathan Gilbert <nathan.gilbert@xxxxxxxxx> wrote:
> 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?
It is NP-complete. You can easily reduce 3-SAT to it.
>
> Thanks in advance,
> NG
.
- References:
- Re: Complexity of graph problems
- From: Nathan Gilbert
- Re: Complexity of graph problems
- Prev by Date: Re: Complexity of graph problems
- Next by Date: SPIN 2006 Last call for papers. DL: December 2, 2005
- Previous by thread: Re: Complexity of graph problems
- Next by thread: SPIN 2006 Last call for papers. DL: December 2, 2005
- Index(es):
Relevant Pages
|
