Abstract
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 NP-trudnym. W tym artykule podejmujemy próbę zastosowania i oceny różnych algorytmów heurystycznych dla kolorowania hipergrafów. Rozważania ogólne poparte są doświadczeniami komputerowymi. Testy zaimplementowanych algorytmów przeprowadzono na hipergrafach losowych.
Author (1)
Cite as
export:
Loading...
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
no. T. 13,
pages 449 - 456,
ISSN: 1732-1166 - Publication year:
- 2007
- Bibliographic description:
- Obszarski P.: Heurystyczne algorytmy szeregowania zadań wieloprocesorowych na procesorach dedykowanych// Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne. -Vol. T. 13., (2007), s.449-456
- Verified by:
- Gdańsk University of Technology
seen 161 times