Search
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.
Cite as
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 148 times