Wyniki wyszukiwania dla: KOLOROWANIE LISTOWE - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: KOLOROWANIE LISTOWE

Wyniki wyszukiwania dla: KOLOROWANIE LISTOWE

  • Listowe kolorowanie grafów

    Publikacja

    - Rok 2002

    W klasycznym modelu kolorowania grafów,kolor przydzielany wierzchołkowi jestograniczony przez regułę zakazującą pokolorowania dwóch sąsiednich wierz-chołków tym samym kolorem. Kolorowanie listowe wprowadza dodatkowe ograni-czenie: każdy wierzchołek posiada z góry określony zbiór dopuszczalnych ko-lorów. Rozważamy jak duża może być różnica pomiędzy liczbą chromatyczną ilistową liczbą chromatyczną oraz dla jakich klas grafów...

  • Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych

    Publikacja

    - Rok 2005

    Szeregowanie jednostkowych zadań 1- i 2-procesorowych z dodatkowym ograniczeniem w postaci zróżnicowanych okien czasowych, w których zadania te mogą być wykonywane zamodelowano przy pomocy listowego kolorowania i multikolorowania krawędzi grafów. Kryteria jakości harmonogramu: maksymalny koszt wykonania zadania w jednostce czasu oraz suma tychże kosztów po wszystkich zadaniach można przedstawić rozszerzając kolorowanie listowe...

  • Parallel scheduling by graph ranking

    Publikacja

    - Rok 2006

    Nr dokum.: 73017Praca dotyczy jednego z nieklasycznych modeli kolorowania grafów - uporządkowanego kolorowania. Celem było uzyskanie wyników, które mogo być wykorzystane w praktycznych zastosowaniach tego modelu, do których należą: równoległe przetwarzanie zapytań w relacyjnych bazach danych, równoległa faktoryzacja macierzy metodą Choleskiego, równoległa asemblacja produktu z jego części składowych. W pracy wskazano uogólnienia...

  • Efficient list cost coloring of vertices and/or edges of some sparse graphs

    Publikacja

    - Rok 2007

    Rozważane jest kolorowanie wierzchołków i krawędzi grafów w modelach klasycznym, totalnym i pseudototalnym z uwzględnieniem dodatkowego ograniczenia w postaci list dostępnych kolorów. Proponujemy wielomianowy algorytm oparty na paradygmacie programowania dynamicznego dla grafów o strukturze drzewa. Wynik ten można uogólnić na grafy o liczbie cyklomatycznej ograniczonej z góry przez dowolnie wybraną stała.

  • The complexity of list ranking of trees

    Publikacja

    Uporządkowane kolorowanie grafu polega na takim etykietowaniu jego wierzchołków, aby każda ścieżka łącząca dwa wierzchołki o tym samym kolorze zawierała wierzchołek o kolorze wyższym. Jeśli każdy wierzchołek posiada dodatkowo listę dozwolonych dla niego etykiet, to mówimy wówczas o uporządkowanym listowym kolorowaniu wierzchołków. W pracy wskazano szereg klas grafów, dla których problem jest trudny: pełne drzewa binarne, drzewa...

    Pełny tekst do pobrania w serwisie zewnętrznym

  • Some results on trading model in a consensus list coloring

    Publikacja

    Konsensusowy model kolorowania grafów - uogólnienie kolorowania listowego, został zdefiniowany przez Mahadeva i Robertsa w 2002 jako użyteczne narzędzie teoretyczne w niektórych zagadnieniach bioinformatycznych. Pozostaje on jednak słabo rozpoznany pod względem własności algorytmicznych. Wykazujemy, że problem kolorowania grafów pełnych w tym modelu jest wielomianowy, co można uogólnić na częściowe k-drzewa przy ustalonym ograniczeniu...