Publikacje
Filtry
wszystkich: 513
Katalog Publikacji
Rok 2008
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować przy pomocy hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy jak przy pomocy modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania, oraz jak rozwiązać problemy dwukryterialne.
-
program verification strategy and edge ranking of graphs
PublikacjaW artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
-
Rearrangeable clos networks C(n,r_1,n^2-1,n,r_2) with certain restrictions for connections
PublikacjaW pracy została zaproponowana nowa metoda sprawdzania przestrajalności pól Closa dla połączeń jeden do wiele. W rozważaniach zakładamy grupowanie połączeń.In the article we will propose new method of checking rearrangeability of multicast Clos networks. In the literature there is no precise method for checking rearrangeability. We focused on three-stage Clos networks without any constraints about fan-out capability. We show the...
-
Scanning networks with cactus topology
PublikacjaThe family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublikacjaW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Some results on trading model in a consensus list coloring
PublikacjaKonsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...
-
Taking advantage of symmetries: gathering of asynchronous oblivious robots on a ring
PublikacjaW pracy rozważano problem rendezvous (spotkania, zebrania) dla zbioru bezpamięciowych robotów umieszczonych na wierzchołkach cyklu nieskierowanego, niewyposażonych w urządzenia komunikacyjne. Przyjęto model systemu rozproszonego występujący w literaturze pod nazwą asynchronicznego systemu z cyklami Look-Compute-Move. Problem istnienia rozwiązania rozwiązano dla wszystkich konfiguracji poczatkowych składających się z więcej niż...
-
The complexity of list ranking of trees
PublikacjaUporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...
-
The maximum edge-disjoint paths problem in complete graphs
PublikacjaRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
Tighter bounds on the size of a maximum P3-matching in a cubic graph
PublikacjaW pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.
-
W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo
Publikacjaw artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1, ..., jn, czas przetwarzania zadania i wynosi pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u,...
-
Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych
PublikacjaUmieszczenie grafu w grafie jest odwzorowaniem pomiędzy parą grafów. Graf umieszczany reprezentuje sieć komunikujących się ze sobą zadań, natomiast graf docelowy dostępną architekturę wykonania tych zadań. Problem polega na takim odwzorowaniu wierzchołków i krawędzi, aby zminimalizować koszty wynikające z potrzeby użycia zastępczych ścieżek w grafie docelowym. W klasycznym modelu przyjmuje się, że oba grafy są proste i ich krawędzie...
Rok 2007
-
A polynomial algorithm for some preemptive multiprocessor task scheduling problems.
Publikacja.
-
Algorytm budowy reprezentacji przedziałowej grafu jako heurystyka dla problemu mapowania DNA
PublikacjaW pracy dokonano analizy przydatności algorytmu Corneil'a budowy reprezentacji przedziałowej grafu jako heurystyki dla problemu tworzenia map fizycznych DNA. Prezentowana analiza dotyczy dwóch osobno rozpatrywanych przypadków, w których do danych wzorcowych wprowadzamy odpowiednio błędy negatywne (reprezentujące niedobór informacji) oraz błędy pozytywne (reprezentujące fałszywe informacje). Rozpatrywany algorytm zachowuje się znacznie...
-
Application of an online judge & contester system in academic tuition
PublikacjaPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
Cooperative mobile guards in grids
PublikacjaPraca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla...
-
Cost minimisation in multi-interface networks
PublikacjaPraca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne.
-
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.
-
Generating fractal tiles using Voronoi diagrams
PublikacjaPraca opisuje szczególną klasę podziałów powierzchni n-wymiarowego torusa na komórki o fraktalnym brzegu. Zbiór komórek przejawia nietypowe własności samopodobieństwa, może zostać użyty do wypełnienia przestrzeni R^n w sposób periodyczny lub aperiodyczny ze zmienną gęstością podziałów. Zaproponowany został algorytm do generowania takich podziałów używając diagramów Woronoja. Opisana metoda może mieć zastosowania w grafice komputerowej.
-
Graph models of clos networks
Publikacja...
-
Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem szeregowania zadań wieloprocesorowych na procesorach dedykowanych można zaprezentować przy pomocy modelu kolorowania krawędzi hipergrafów. Hipergrafem nazywamy pewne uogólnienie grafu, w którym krawędzie mogą zawierać dowolnie wiele wierzchołków. Model taki pozwala symulować rozmaite zjawiska praktyczne oraz teoretyczne. Kolorowanie hiperkrawędzi hipergrafów jest uogólnieniem kolorowania krawędzi grafów, zatem jest problemem...
-
Hiperheurystyki w kolorowaniu grafów
PublikacjaHiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla...
-
Kolorowanie końcówkowe multidrzew
PublikacjaW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Kształcenie umiejętności pracy w zespole wśród studentów informatyki
PublikacjaW pracy zaprezentowano przedmiot ''Projekt grupowy'' prowadzony na Wydziale ETI Politechniki Gdańskiej, którego celem jest przekazanie studentom wiedzy i wykształcenie umiejętności w zakresie: pracy zespołowej, prowadzenia rozmów z klientem zlecającym pracę projektowania i wytwarzania produktów z wykorzystaniem najnowszych technologii informacyjnych i telekomunikacyjnych oraz wytwarzania i utrzymania dokumentacji projektowej. W...
-
Model formalny dla problemu lokalizacji błędów w kodzie programu
PublikacjaIstnieje szereg sposobów badania poprawności programów komputerowych. W niniejszym referacie podejmujemy problem automatycznego testowania oprogramowania przy założeniu, iż dany jest zbiór testów (asercji) dla poszczególnych fragmentów kodu. Dla uproszczenia analizy zakładamy, że badany fragment kodu zawiera dokładnie jeden błąd, co nie zmniejsza ogólności rozważań. W artykule analizujemy praktyczne aspekty powyższego problemu...
-
Modelowanie zagrożeń w sieciach komputerowych
PublikacjaW artykule przedstawiono problematykę zagrożeń w sieciach komputerowych. Dokonano przeglądu obszarów zastosowań Internetu ze szczególnym zwróceniem uwagi na zagadnienia bezpieczeństwa. Przedstawiono szereg strategii oraz rozwiązań o charakterze praktycznym w obszarach polityki bezpieczeństwa realizowanych przez różnego typu organizacje. Wyszczególniono zasady szeroko pojętej polityki bezpieczeństwa. Sklasyfikowano ataki oraz nielegalne...
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
Packing [1,Delta]-factors in graphs of small degree
PublikacjaRozważano problem znalezienia w grafie zadanej liczby k krawędziowo rozłącznych [1,Delta]-faktorów, gdzie Delta oznacza stopień grafu. Problem ten można rozwiązać w czasie liniowym dla k=2, jest on jednak NP-trudny dla każdego k>=3. Pokazano, że wariant minimalizacjny problemu dla k=2 jest NP-trudny dla grafów planarnych podkubicznych, jednak w ogólności istnieje algorytm (42 Delta - 30) / (35 Delta - 21) - aproksymacyjny.
-
Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania
PublikacjaW pracy rozważany jest następujący, jednoprocesorowy problem szeregowania zadań czasowo-zależnych. danych jest n+1 zadań o czasach wykonywania postaci pi = a + bisi, gdzie si oznacza czas rozpoczęcia wykonywania i-tego zadania, a > 0, bi > 0, i = 0, 1, ..., n. wszystkie zadania są niepodzielne i dostępne w chwili t0 = 0. należy znaleźć harmonogram minimalizujący łączny czas zakończenia. w pracy przedstawiono algorytm, który, o...
-
Porównywanie topologii drzew i sieci filogenetycznych z wykorzystaniem metryki błędu
PublikacjaPodstawowymi modelami historii ewolucji organizmów są drzewa i sieci filogenetyczne. Ponieważ algorytmy konstrukcji filogenów zwracają różne wyniki dla tych samych danych wejściowych, powstaje problem oceny, który filogen najlepiej reprezentuje historię ewolucji dla zadanego zbioru gatunków. W pracy podano definicję metryki dla przestrzeni drzew o n liściach, zwanej metryką błędu. Dokonano przeglądu miar odległości na przestrzeni...
-
Proceduralne modelowanie stworów w Suboceanic
PublikacjaSuboceanic to niewielki program wykonywalny zajmujący 50 kilobajtów. Został zaprezentowany na party demoscenowym Assembly 2005 w kategorii intro 64k. Efektem działania programu jest multimedialna animacja, w której zarówno obraz jak i dźwięk generowany jest w czasie rzeczywistym. Ta praca opisuje szczegółowo algorytmy opracowane podczas produkcji tego intra do generowania proceduralnych stworów i roślin. Opisana metoda polega na...
-
Przechwytywanie obiektów poruszających się z ograniczoną prędkością
PublikacjaKrawędziowa liczba przeszukiwawcza grafu informuje nas ilu mobilnych agentów, przykładowo jednostek policji, jest niezbędnych do przechwycenia poruszającego się z dowolnie dużą prędkością uciekiniera w danym grafie. Podczas praktycznych zastosowań modelu w systemach bezpieczeństwa rzadko jednak spotyka się jednostki poruszające się z nieograniczoną prędkością. W pracy tej pokazujemy, że agenci mogą wykorzystać fakt ograniczonej...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
Witryna inrenetowa w funkcjonowaniu szkoły
PublikacjaW artykule przedstawiono problematykę funkcjonowania witryn internetowych w środowisku edukacyjnym. Przeanalizowano aspekty zarówno natury technologicznej jak i informacyjnej. Zaprezentowano technologie informatyczne i internetowe zorientowane na tworzenie witryn www. Przeanalizowano potrzeby funkcjonalne dla witryn szkolnych i edukacyjnych. Zwrócono uwagę na ich ukierunkowanie na grupy odbiorcze. Pokazano reprezentatywne przykłady...
-
Zastosowania trójkątnych płytek w grafice komputerowej
PublikacjaPraca opisuje metody pokrywania trójkątnymi płytkami dowolnych powierzchni trójwymiarowych reprezentowanych przez siatki trójkątne. Omówione są znane metody konstruowania i układania trójkątnych płytek oraz ich optymalizacja algorytmami kolorowania grafów. Zaproponowana jest ulepszona hybrydowa metoda, umożliwiająca pokrycie dowolnej powierzchni wzorem, który wymaga kierunkowego uporządkowania.
-
Zwarte końcówkowe kolorowanie grafów
PublikacjaPraca dotyczy jednego z nowych modeli kolorowania grafów, tzw. zwartego końcówkowego kolorowania. Praca zawiera definicję modelu, informacje o jego zastosowaniach, dolne i górne oszacowania na liczbę kolorów oraz wartości dokładne zwartego końcówkowego indeksu dla wybranych klas grafów: ścieżek, cykil, gwiazd, kół, grafów pełnych i innych.
Rok 2006
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
An approximation algorithm for maximum P3-packing in subcubic graphs
PublikacjaW pracy podano algorytm 4/3-przyliżony dla trudnego obliczeniowo problemu umieszczania wierzchołkowo rozłącznych dwukrawędziowych ścieżek w grafach o stopniu maksymalnym 3 i stopniu minimalnym 2. Poprawiono tym samym wcześniejsze wyniki dla grafów kubicznych (A. Kelmans, D. Mubayi, Journal of Graph Theory 45, 2004).
-
An efficient algorithm for mobile guarded guards in simple grids
PublikacjaW pracy rozważono problem strzeżenia ortogonalnych krat dwuwymiarowych przez mobilne straże strzeżone. Podano algorytmy wielomianowe m.in. dla przypadku krat prostych i dla przypadku krat bez przeszkód w kierunku poziomym (pionowym).
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł dopasowań
PublikacjaBiologia molekularna jest obecnie bardzo dynamicznie rozwijającą się dziedziną nauki. Wzrost mocy obliczeniowej komputerów pozwala na coraz szybszą i dokładniejszą analizę wielocząsteczkowych biologicznych polimerów. Poniższy artykuł przedstawia jeden z modułów programu AlignGator - modułowego systemu przeznaczonego do analizy DNA. Omawiany moduł pozwala na tworzenie, oraz edycję wielodopasowań. W początkowej części artykułu opisane...
-
Aplikacja wspomagająca przetwarzanie sekwencji dna: moduł edycji chromatogramu
PublikacjaModuł edycji chromatogramu jest częścią większej aplikacji, służącej do wspomagania przetwarzania danych pochodzących z sekwencjonowania DNA. Aplikacja skonstruowana jest z odrębnych, samodzielnych programów, które współpracują dwiema drogami - poprzez popularne formaty plików, co umożliwia wprowadzenie do modułów danych opracowanych częściowo w aplikacjach zewnętrznych, oraz poprzez przesyłanie danych pomiędzy modułami, co usprawnia...
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublikacjaPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
Chromatic scheduling of 1- and 2-processor uet tasks on dedicated machines with availability constraints.
PublikacjaRozważono uogólnienie klasycznego szeregowania jednostkowych zadań jedno- i dwuprocesorowych na maszynach dedykowanych. Przyjęty model pozwala na naturalne wprowadzenie wszystkich klasycznych kryteriów optymalizacyjnych dla harmonogramów. Zaproponowano algorytmy wielomianowe dla systemów rzadkich.
-
Efficient parallel query processing by graph ranking
PublikacjaW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
Energy optimisation in resilient self-stabilizing processes
PublikacjaW pracy rozważa się rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowy samostabilizujący algorytm kolorowania grafów oparty na konstrukcji drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm z gwarantowaną wielomianową liczbą ruchów, który dokładnie koloruje grafy dwudzielne.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
Fault tolerant guarding of grids
PublikacjaW pracy rozważano problem strzeżenia krat dwuwymiarowych przez dwa niezależne zespoły straży. Wykazano, że zagadnienie minimalizacyjne jest NP-trudne i zaproponowano dla niego wielomianowy algorytm 6/5-przybliżony.
-
Formalizm i metody szeregowania zadań dla potrzeb redukcji poboru mocy cyfrowych układów CMOS
PublikacjaW pracy przedstawiono związki pomiędzy modelami formalnymi stosowanymi w klasycznym szeregowaniu zadań a metodami wykorzystywanymi w syntezie wysokiego poziomu układów cyfrowych CMOS. Zagadnienia optymalizacyjne pojawiające się w obu tych problemach mogą być w pewnym sensie transformowalne. Pozwala to na przenoszenie wybranych metod rozwiązań z jednego problemu do drugiego.
-
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
PublikacjaPrzedstawienie 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...