Search results for: HIPERGRAF

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

• Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych

  Publication

  • P. Obszarski

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

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

• Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych

  Publication

  • P. Oszarski
  • J. Dąbrowski

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

  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. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...

• Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych

  Publication

  • P. Obszarski

  - Year 2008

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

• Duże rozgłoszeniowe pola Closa

  Publication

  • A. Jastrzębski

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

  W pracy pokazano nowe podejście do blokowalności dużych rozgłoszeniowych pól Closa. Przedstawione zostały także dowody na blokowalność pola C(n,r_1,n^2-1,n,r_2) oraz pola C(n,r_1,n^2,n,r_2), w których użyto ekstremalną teorię grafów i hipergrafów.

• Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

  Publication

  • P. Obszarski
  • M. Kubale

  - Automatyka / Automatics - Year 2009

  W artykule rozważamy problem szeregowania jednostkowych zadań wieloprocesorowych na procesorach dedykowanych z repetycją zadań i ograniczeniami dostępności. Prezentujemy zebrane wyniki złożoności dla różnych typów instancji powyższego problemu szeregowania z kryteriami długości harmonogramu, sumy czasów zakończenia zadań i kosztu całkowitego. Problem ten opisujemy modelem kolorowania krawędzi różnych klas hipergrafów.

  Full text available to download

• Szeregowanie zadań wieloprocesorowych na maszynach dedykowanych w modelu hipergrafowym

  Publication

  • P. Obszarski

  - Year 2009

  Ostatnimi czasy obserwujemy dwie tendencje w działalności człowieka. Pierwszą jest specjalizacja. Wobec rosnącej wiedzy i zaawansowania technologicznego, niemożliwym stało się, by jedna osoba mogła wiedzieć i robić wszystko. Podobnie jest z maszynami, które im są bardziej wyspecjalizowane tym są tańsze i tym lepiej wykonują swoje zadania. Druga tendencja to wieloprocesorowość, którą inaczej możemy nazwać pracą zespołową. Efekt...