Article View: pl.comp.lang.c
Article #529Re: V Olimpiada Informatyczna
From: Marek Futrega
Date: Tue, 20 Jan 1998 16:03
Date: Tue, 20 Jan 1998 16:03
23 lines
1487 bytes
1487 bytes
On Tue, 20 Jan 1998, Michal Kaczmarczyk wrote:
> On Tue, 6 Jan 1998, Marek Futrega wrote:
>
> > Zadanie AB-Slowa - problem jest NP-zupelny, zatem jedyne co mozesz
> > szukac to roznego rodzaju heurystyki.
>
> Czy aby na pewno? Mi się wydaje że znalazłem jakis algorytm wielomianowy,
^^^^^^^^^^
> ale nie zdażyłem go zaimplementować na czas, więc go zarzuciłem :-(
Tylko Ci sie wydaje.
Znajdywanie niezaleznego zbioru wierzcholkow w grafie jest NP-zupelne.
[a do tego sprowadza sie przeciez zadanie]
Wiecej na temat tego zadania -> adam.borowski@zodiac2.mimuwu.edu.pl :)
pozdrawiam,
Marek Futrega - MAF
___
marek.futrega@students.mimuw.edu.pl
http://polbox.com/f/futer
Technical Details
Message-ID:
<Pine.LNX.3.95.980120165930.334B-100000@zodiac2.mimuw.edu.pl>Path:
mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!pingwin.icm.edu.pl!news.icm.edu.pl!uw.edu.pl!zodiac2.mimuw.edu.pl!mf174715References:
<68lk9n$2hp@h1.uw.edu.pl> <Pine.LNX.3.95.980106140438.21336A-100000@zodiac2.mimuw.edu.pl> <Pine.LNX.3.96.980120153804.23418E-100000@fox>Show Full Headers
Complete Article Headers
Path: mbox-mo1.pugleaf.net!news-archive.icm.edu.pl!pingwin.icm.edu.pl!news.icm.edu.pl!uw.edu.pl!zodiac2.mimuw.edu.pl!mf174715 From: Marek Futrega <mf174715@zodiac2.mimuw.edu.pl> Newsgroups: pl.comp.lang.c Subject: Re: V Olimpiada Informatyczna Date: Tue, 20 Jan 1998 17:03:09 +0100 Organization: A poorly-installed usenet news reader Lines: 26 Message-ID: <Pine.LNX.3.95.980120165930.334B-100000@zodiac2.mimuw.edu.pl> References: <68lk9n$2hp@h1.uw.edu.pl> <Pine.LNX.3.95.980106140438.21336A-100000@zodiac2.mimuw.edu.pl> <Pine.LNX.3.96.980120153804.23418E-100000@fox> NNTP-Posting-Host: zodiac2.mimuw.edu.pl Mime-Version: 1.0 In-Reply-To: <Pine.LNX.3.96.980120153804.23418E-100000@fox> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit