Search results for: KOLOROWANIE RADIOWE

• Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.

  Publication

  • A. Kosowski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Year 2003

  Praca zawiera charakterystykę suboptymalnych algorytmów antypodalnego kolorowania grafów, stanowiących adaptację algorytmów sekwencyjnych S, SL, LF stosowanych przy klasycznym kolorowaniu grafów. Dla tych algorytmów wskazano grafy dość trudne i trudne do pokolorowania (HC i SHC). Porównano ich funkcję dobroci i rozpiętości uzyskiwanych pokolorowań dla grafów o różnej gęstości krawędziowej.

• Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.

  Publication

  • M. Kubale
  • A. Kosowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Year 2002

  W pracy opisane są podstawowe zasady i właściwości radiowego kolorowania grafów. Podane są oszacowania radiowej liczby chromatycznej grafu w przypadku ogólnym, dla ścieżek i cykli oraz dokładne wartości radiowej liczby chromatycznej dla grafów pełnych k-dzielnych, kół i dwugwiazd. Zamieszczono także przykładowe wyniki porównania dobroci suboptymalnych, sekwencyjnych algorytmów radiokolorowania grafów.

• Kolorowanie hipergrafów

  Publication

  • M. Kubale
  • K. Piwakowski
  • P. Obszarski

  - Year 2006

  Hipergraf to struktura stanowiąca pewne uogólnienie grafu. Oprócz tradycyjnych krawędzi dwuelementowych dopuszcza ona także krawędzie, które zawierają inną, przeważnie większą liczbę wierzchołków. W tej pracy pokażemy kilka modeli kolorowania hipergrafów, takich jak kolorowanie krawędzi, kolorowanie wierzchołków i tzw. CD-kolorowanie, przedstawimy ich podstawowe własności oraz wskażemy zastosowania.

• Kolorowanie końcówkowe multidrzew

  Publication

  • R. Janczewski
  • M. Małafiejski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Year 2007

  W 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.

• Rozproszone kolorowanie grafów

  Publication

  • Ł. Kuszner

  - Year 2006

  W pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.

• Harmoniczne kolorowanie grafów

  Publication

  • M. Kubale

  - Year 2002

  W rozdziale omówiono tzw. harmoniczne kolorowanie grafów, które jest odmia-ną klasycznego kolorowania wierzchołków grafów. Podano najważniejsze własno-ści tego sposobu kolorowania grafów i jego potencjalne zastosowanie w radio-komunikacji lotniczej i projektoaniu funkcji mieszających. Podano równieżtzw. algorytm degresywny, który koloruje każdy graf za pomocą liczby kolorównie przekraczającej w dwójnasób harmonicznej liczby...

• Kontrastowe kolorowanie grafów

  Publication

  • R. Janczewski

  - Year 2002

  Niniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana zostałajego definicja i podstawowe własności, zastosowania oraz złożoność oblicze-niowa problemów rozważanych w ramach tej dziedziny.

• Cyrkularne kolorowanie grafów

  Publication

  • A. Nadolski

  - Year 2002

  Rozdział zawiera definicje oraz większość znanych własności cyrkularnego ko-lorowania grafów w wersji wierzchołkowej oraz krawędziowej. Podano znanezwiązki tego rodzaju kolorowania z innymi modelami kolorowania grafów. Wpracy zawarto także przykłady możliwych zastosowań cyrkularnego kolorowaniaw szeregowaniu zadań.

• Sprawiedliwe kolorowanie grafów

  Publication

  • H. Furmańczyk

  - Year 2002

  Kolorowanie sprawiedliwe jest kolorowaniem klasycznym z dodatkowym ograni-czeniem: chcemy, aby krotności użycia kolorów różniły się co najwyżej o je-den. W pracy przedstawiamy wyniki dotyczące sprawiedliwego kolorowania wie-rzchołków, krawędzi oraz obu tych elementów jednocześnie. Ponieważ problemjest NP-zupełny w ogólnym przypadku, poszukuje się algorytmów przybliżonych.Przedstawiamy dwa takie algorytmy.

• Listowe kolorowanie grafów

  Publication

  • K. Piwakowski

  - Year 2002

  W klasycznym modelu kolorowania grafów,kolor przydzielany wierzchołkowi jestograniczony przez regułę zakazującą pokolorowania dwóch sąsiednich wierz-chołków tym samym kolorem. Kolorowanie listowe wprowadza dodatkowe ograni-czenie: każdy wierzchołek posiada z góry określony zbiór dopuszczalnych ko-lorów. Rozważamy jak duża może być różnica pomiędzy liczbą chromatyczną ilistową liczbą chromatyczną oraz dla jakich klas grafów...