Wyszukiwarka
Abstrakt
Przedstawienie rozwiązań problemów kombinatorycznych w postacipermutacji daje podstawy do konstrukcji algorytmów lokalnychposzukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje prowadzącedo generowania sąsiedztwa rozwiązania to zamiana dwóch elementówlub przesunięcie elementu permutacji. W artykule wskazujemy metodępozwalającą na wykonanie takich operacji w czasie $O(m)$, przy założeniu, że dane jest drzewo eliminacji wyjściowej permutacji.
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język:
- polski
- Rok wydania:
- 2006
- Opis bibliograficzny:
- Dereniowski D.: Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów// Zeszyty Naukowe Politechniki Śląskiej.. -., nr. z. 143 (2006), s.51-56
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 67 razy