Search results for: algorytmy grafowe

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

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

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

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

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

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

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

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

• Joanna Raczek dr inż.

  People

  Department of Algorithms and Systems Modelling

  Employment 2003 -- 2019: Faculty of Applied Physics and Mathematics, Gdańsk University of Technology. 2019 - present: Faculty of Electronic, Informatics and Telecominications, Gdańsk University of Technology. Education May 2007: Doctor of Philosophy in Mathematics, University of Gdańsk. Doctoral dissertation: "Paired domination and doubly domination in graphs". Supervisor: dr hab. Jerzy Topp. 2000 -- 2004 Bachelor of Science...

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

  Publication

  • A. Kosowski
  • Ł. Kuszner

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