Wyniki wyszukiwania dla: algorytmy grafowe

• Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.

  Publikacja

  • A. Kosowski

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Rok 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.

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

  Publikacja

  • Ł. Kuszner

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

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

  Publikacja

  • R. Janczewski

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

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

  Publikacja

  • A. Kosowski
  • Ł. Kuszner

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Rok 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.

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

  Publikacja

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

  - Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne - Rok 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.

• Zastosowanie algorytmów rojowych do kolorowania grafów

  Publikacja

  • P. Obszarski
  • K. Piwakowski

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

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

  Publikacja

  • Ł. Kuszner
  • A. Kosowski

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

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

  Publikacja

  • M. Kubale
  • A. Kosowski

  - Zeszyty Naukowe Politechniki Śląskiej. Automatyka - Rok 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.

• Joanna Raczek dr inż.

  Osoby

  Katedra Algorytmów i Modelowania Systemów

  Wykształcenie 1997 -- 2001 Studia inżynierskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2001 -- 2003 Studia magisterskie, Wydział Fizyki Technicznej i Matematyki Stosowanej, Politechnika Gdańska. Kierunek: Matematyka, specjalność: Matematyka Stosowana. 2000 -- 2004 Studia inżynierskie, Wydział Elektroniki, Informatyki i Telekomunikacji,...

• Self-stabilizing algorithms for graph coloring with improved performance guarantees

  Publikacja

  • A. Kosowski
  • Ł. Kuszner

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