Abstract
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.
Author (1)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language:
- Polish
- Publication year:
- 2006
- Bibliographic description:
- 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
- Verified by:
- Gdańsk University of Technology
seen 67 times