Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Minimalne pokrycie wierzchołkowe

251 views
Skip to first unread message

Jakub Debski

unread,
Jan 26, 2008, 2:46:14 PM1/26/08
to
Witam,

Jednym z problemów NP-zupełnych jest minimalne pokrycie wierzchołkowe
grafu. Czy znacie może biblioteki lub oprogramowanie (darmowe lub
komercyjne) wspomagające rozwiązywanie tego problemu poprzez stosowanie
różnych heurystyk i algorytmów aproksymacyjnych?
Nawet rozwiązania suboptymalne byłyby zadowalające.

pozdrawiam
Jakub


Piotr Dembiński

unread,
Jan 26, 2008, 3:51:55 PM1/26/08
to
Jakub Debski <debski...@wp.pl> writes:

Może poszukać najpierw minimalnego drzewa rozpinającego dla każdego
spójnego podgrafu krawędziowego danego grafu?

Piotr Dembiński

unread,
Jan 26, 2008, 4:04:02 PM1/26/08
to
Jakub Debski <debski...@wp.pl> writes:

Może poszukać najpierw minimalnego drzewa rozpinającego dla każdego
spójnego podgrafu grafu krawędziowego danego grafu?

A.L.

unread,
Jan 26, 2008, 5:30:22 PM1/26/08
to
On Sat, 26 Jan 2008 20:46:14 +0100, Jakub Debski <debski...@wp.pl>
wrote:

Gdzie to zadali?...

A.L.

Jakub Debski

unread,
Jan 26, 2008, 5:58:41 PM1/26/08
to
> Gdzie to zadali?...

W pracy. Problem analizy danych, który da się sprowadzić do powyższego.

pozdrawiam
Jakub


A.L.

unread,
Jan 26, 2008, 6:08:26 PM1/26/08
to
On Sat, 26 Jan 2008 23:58:41 +0100, Jakub Debski <debski...@wp.pl>
wrote:

>> Gdzie to zadali?...

Sprawdz biblioteke zwana LEDA. To chyba najwieksza biblioteka
algorytmow grafowych

A.L.

Jakub Debski

unread,
Jan 26, 2008, 6:23:41 PM1/26/08
to
> Sprawdz biblioteke zwana LEDA. To chyba najwieksza biblioteka
> algorytmow grafowych

Biblioteka rzeczywiście rozbudowana, ale vertex cover niestety w niej
nie ma.

pozdrawiam
Jakub


A.L.

unread,
Jan 26, 2008, 7:48:04 PM1/26/08
to
On Sun, 27 Jan 2008 00:23:41 +0100, Jakub Debski <debski...@wp.pl>
wrote:

>> Sprawdz biblioteke zwana LEDA. To chyba najwieksza biblioteka

No to sprawdz ta, ale slyszelem ze kiepska

http://www.jgrapht.org/javadoc/org/jgrapht/alg/VertexCovers.html

A.L.

Jakub Debski

unread,
Jan 26, 2008, 8:03:02 PM1/26/08
to
> No to sprawdz ta, ale slyszelem ze kiepska
> http://www.jgrapht.org/javadoc/org/jgrapht/alg/VertexCovers.html

Algorytmy w jgrapht to najprostsze przykłady z książek dla studentów,
których zaimplementowanie to max. kilkanaście minut. W temacie vertex
cover w ostatnich latach sporo się dzieje, ale oprócz licznych
artykułów z matematycznymi teoriami, kodu je potwierdzającego brak.
Najlepsze co na razie znalazłem to:
http://www.geocities.com/dharwadker/vertex_cover/

pozdrawiam
Jakub


0 new messages