Search results for: ALGORYTM KOLOROWANIA

• Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów

  Publication

  • R. Janczewski
  • Ł. Kuszner
  • M. Małafiejski
  • A. Nadolski

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

  W artykule autorzy proponują algorytm przybliżony dla cylkularnego kolorowania krawędzi grafu. Przedstawione są oszacowania na złożoność obliczeniową tego algorytmu, a także wyniki testów na grafach o małej liczbie wierzchołków jak i na grafach losowych.

• Algorytm samostabilizujący dla problemu kolorowania krawędzi grafu.

  Publication

  • Ł. Kuszner
  • A. Nadolski
  • R. Janczewski

  - Year 2004

  Referat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu. Jest to prawdopodobnie pierwszy algorytm krawędziowego kolorowania grafów w tym modelu. Rozważania teoretyczne zostały poparte eksperymentami komputerowymi.

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

• Przybliżone algorytmy uporządkowanego kolorowania krawędzi multidrzew.

  Publication

  • D. Dereniowski
  • R. Janczewski

  - Year 2004

  Niniejszy referat omawia zagadnienie uporządkowanego kolorowania krawędzi multidrzew. Opisano w nim dwa przybliżone algorytmy dla tego problemu, zbadano ich własności teoretyczne oraz przedstawiono wyniki testów komputerowych, jakim zostały poddane.

• Samostabilizujące się algorytmy wierzchołkowego kolorowania grafów.

  Publication

  • Ł. Kuszner

  - Year 2004

  Artykuł jest poświęcony kolorowaniu grafów w modelu rozproszonym. Podano schemat konstruowania samostabilizujących się algorytmów wierzchołkowego kolorowania grafów z możliwością nadawania wierzchołkom priorytetów. W oparciu o tę technikę skonstruowano samostabilizujący się algorytm LF który został szczegółowo opisany. Przeprowadzono również testy komputerowe porównując algorytm LF ze znanymi wcześniej algorytmami samostabilizującymi.

• Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów

  Publication

  • Ł. Kuszner
  • A. Kosowski

  - Year 2006

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

• Zachłanne algorytmy kolorowania grafów w modelu rozproszonym

  Publication

  • A. Kosowski
  • Ł. Kuszner

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

  W artykule porównano cztery rozproszone algorytmy kolorowania grafów. Zaprezentowano wyniki eksperymentów komputerowych, w których badano liczbę rund i kolorów uzyskanych dla grafów losowych.

• Zastosowanie algorytmów rojowych do kolorowania grafów

  Publication

  • P. Obszarski
  • K. Piwakowski

  - Year 2006

  Przedstawiamy sposób adaptacji heurystycznej metody przeszukiwania PSO (ang. Particle Swarm Optimization) do znajdowania suboptymalnych pokolorowań wierzchołkowych grafów prostych. Prezentujemy sposób przeprowadzenia eksperymentów obliczeniowych oraz ich wyniki.

• Uogólnione algorytmy zachłanne w kontrastowym kolorowaniu grafów.

  Publication

  • R. Janczewski

  - Year 2004

  Niniejszy referat poświęcony jest uogólnionym algorytmom zachłannym. Zawiera ich opis, krótką analizę ich własności oraz wyniki testów komputerowych którym zostały poddane.

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