Filtry
wszystkich: 3515
wybranych: 3212
-
Katalog
- Publikacje 3212 wyników po odfiltrowaniu
- Konferencje 3 wyników po odfiltrowaniu
- Osoby 65 wyników po odfiltrowaniu
- Wynalazki 2 wyników po odfiltrowaniu
- Projekty 11 wyników po odfiltrowaniu
- Zespoły Badawcze 5 wyników po odfiltrowaniu
- Aparatura Badawcza 1 wyników po odfiltrowaniu
- Kursy Online 120 wyników po odfiltrowaniu
- Wydarzenia 11 wyników po odfiltrowaniu
- Dane Badawcze 85 wyników po odfiltrowaniu
Filtry wybranego katalogu
wyświetlamy 1000 najlepszych wyników Pomoc
Wyniki wyszukiwania dla: ALGORYTM KOLOROWANIA
-
Algorytm przybliżony dla cyrkularnego kolorowania krawędzi grafów
PublikacjaW 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.
-
Algorytm samostabilizujący dla problemu kolorowania krawędzi grafu.
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu. Jest to prawdopodobnie pierwszy algorytm krawędziowego kolorowania grafów w tym modelu. Rozważania teoretyczne zostały poparte eksperymentami komputerowymi.
-
Sekwencyjne algorytmy antypodalnego kolorowania radiowego grafów.
PublikacjaPraca 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.
-
Przybliżone algorytmy uporządkowanego kolorowania krawędzi multidrzew.
PublikacjaNiniejszy referat omawia zagadnienie uporządkowanego kolorowania krawędzi multidrzew. Opisano w nim dwa przybliżone algorytmy dla tego problemu, zbadano ich własności teoretyczne oraz przedstawiono wyniki testów komputerowych, jakim zostały poddane.
-
Samostabilizujące się algorytmy wierzchołkowego kolorowania grafów.
PublikacjaArtykuł 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.
-
Samostabilizujący się algorytm kolorowania grafów dwudzielnych i kaktusów
PublikacjaW 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.
-
Zachłanne algorytmy kolorowania grafów w modelu rozproszonym
PublikacjaW 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.
-
Zastosowanie algorytmów rojowych do kolorowania grafów
PublikacjaPrzedstawiamy 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.
-
Uogólnione algorytmy zachłanne w kontrastowym kolorowaniu grafów.
PublikacjaNiniejszy 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.
-
Algorytmy radiowego kolorowania grafów. XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych.
PublikacjaW 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.
-
Self-stabilizing algorithms for graph coloring with improved performance guarantees
PublikacjaW 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.
-
Eksperymenty z zastosowanie algorytmów genetycznych do problemu kolorowania grafów
PublikacjaNiniejsza praca przedstawia wykorzystanie algorytmów genetycznych (AG) do problemu kolorowania wierzchołków grafu (GCP). Przeprowadzono szereg symulacji mających na celu porównanie skuteczności operatorów krzyżownia, mutacji i selekcji oraz sposobu generacji i parametrów populacji. Uzyskane wyniki pokazały znaczną przewagę operatorów korzystających z wiedzy o problemie nad operatorami losowymi. Dla wybranej konfiguracji algorytmu...
-
Self-stabilizing algorithm for edge-coloring of graphs
PublikacjaReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
Parallel tabu search for graph coloring problem
PublikacjaTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
A self-stabilizing algorithm for finding a spanning tree in a polynomial number of moves
PublikacjaW 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 znajdowania drzewa spinającego. Zgodnie z naszą wiedzą jest to pierwszy algorytm dla tego problemu z gwarantowaną wielomianową liczbą ruchów.
-
Efficient list cost coloring of vertices and/or edges of some sparse graphs
PublikacjaRozważ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.
-
Kolorowanie hipergrafów
PublikacjaHipergraf 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.
-
Kolorowanie końcówkowe multidrzew
PublikacjaW pracy przedstawiono nowy model kolorowania grafów, mianowicie kolorowanie końcówkowe. Naszkicowano związki łączące ten model z klasycznymi modelami kolorowania oraz przedstawiono wielomianowy algorytm optymalnie końcówkowo kolorujący multidrzewa.
-
Cyrkularne kolorowanie grafów
PublikacjaRozdział zawiera definicje oraz większość znanych własności cyrkularnego ko-lorowania grafów w wersji wierzchołkowej oraz krawędziowej. Podano znanezwiązki tego rodzaju kolorowania z innymi modelami kolorowania grafów. Wpracy zawarto także przykłady możliwych zastosowań cyrkularnego kolorowaniaw szeregowaniu zadań.
-
Sprawiedliwe kolorowanie grafów
PublikacjaKolorowanie sprawiedliwe jest kolorowaniem klasycznym z dodatkowym ograni-czeniem: chcemy, aby krotności użycia kolorów różniły się co najwyżej o je-den. W pracy przedstawiamy wyniki dotyczące sprawiedliwego kolorowania wie-rzchołków, krawędzi oraz obu tych elementów jednocześnie. Ponieważ problemjest NP-zupełny w ogólnym przypadku, poszukuje się algorytmów przybliżonych.Przedstawiamy dwa takie algorytmy.
-
Harmoniczne kolorowanie grafów
PublikacjaW rozdziale omówiono tzw. harmoniczne kolorowanie grafów, które jest odmia-ną klasycznego kolorowania wierzchołków grafów. Podano najważniejsze własno-ści tego sposobu kolorowania grafów i jego potencjalne zastosowanie w radio-komunikacji lotniczej i projektoaniu funkcji mieszających. Podano równieżtzw. algorytm degresywny, który koloruje każdy graf za pomocą liczby kolorównie przekraczającej w dwójnasób harmonicznej liczby...
-
Kontrastowe kolorowanie grafów
PublikacjaNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana zostałajego definicja i podstawowe własności, zastosowania oraz złożoność oblicze-niowa problemów rozważanych w ramach tej dziedziny.
-
Klasyczne kolorowanie grafów
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach pro-stych. Oprócz podstawowych definicji podane zostały najczęściej stosowanemetody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przeglądznanych benczmarków dla podanych metod w kontekście klasycznego modelu kolo-rowania.
-
Listowe kolorowanie grafów
PublikacjaW 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...
-
Sumacyjne kolorowanie grafów
PublikacjaW tym rozdziale, oprócz szczegółowego zaprezentowania koncepcji sumy chroma-tycznej, jej własności oraz wyników z nią związanych, dokonano analizy zło-żoności problemu sumacyjnego kolorowania dla wybranych klas grafów, w szcze-gólności rozróżniono klasy grafów, dla których problem sumacyjnego kolorowa-nia można rozwiązać w czasie wielomianowym oraz przypadki NP-trudne.
-
Rozproszone kolorowanie grafów
PublikacjaW pracy zaprezentowano nowy rozproszony algorytm kolorowania grafów. Przeprowadzone eksperymenty pokazują, że daje on lepsze wyniki niż znany wcześniej algorytm trywialny.
-
Zwarte kolorowanie krawędzi
PublikacjaPraca omawia model zwartego kolorowania grafów i jego zastosowania w szere-gowaniu zadań. Podano podstawowe właściwości kolorowania zwartego, a takżegrafów dających się w ten sposób kolorować. przedstawiono szereg rodzin gra-fów dwudzielnych posiadających zwarte pokolorowania. Zdefiniowano też pewnąmiarę ''niezwartości'' kolorowania krawędziowego zwaną stratnością.
-
Rozproszone kolorowanie grafów
PublikacjaW pracy rozważany jest rozproszony model obliczeń, w którym struktura systemu jest reprezentowana przez graf bezpośrednich połączeń komunikacyjnych. W tym modelu podajemy nowe, rozproszone algorytmy kolorowania grafów wraz z dokładną analizą teoretyczną i wynikami eksperymentów obliczeniowych.
-
Hiperheurystyki w kolorowaniu grafów
PublikacjaHiperheurystyki to jeden z nowych trendów w technice obliczeniowej. Można je zdefiniować jako algorytmy, które wykorzystują zdefiniowany zbiór prostych heurystyk do znalezienia przybliżonego rozwiązania. Celem algorytmu jest znalezienie takiej sekwencji uruchamiania tych prostych operacji, która będzie dawała najlepsze rozwiązanie dla danej instancji problemu lub danej klasy instancji problemu. W pracy zdefiniowano heurystyki dla...
-
Zwarte końcówkowe kolorowanie grafów
PublikacjaPraca dotyczy jednego z nowych modeli kolorowania grafów, tzw. zwartego końcówkowego kolorowania. Praca zawiera definicję modelu, informacje o jego zastosowaniach, dolne i górne oszacowania na liczbę kolorów oraz wartości dokładne zwartego końcówkowego indeksu dla wybranych klas grafów: ścieżek, cykil, gwiazd, kół, grafów pełnych i innych.
-
Uporządkowane kolorowanie wierzchołków grafów
PublikacjaW pracy przedstawiamy stosunkowo nowy model kolorowania grafów, mianowicie kolorowanie uporządkowane. Po scharakteryzowaniu potencjalnych zastosowań tego modelu przedstawiamy liniowy algorytm kolorowania grafów w sposób przybliżony. Pokazujemy klasy grafów, które ten algorytm koloruje optymalnie i klasy grafów, dla których błąd pokolorowania może być dowolnie duży. Przedstawiamy również doświadczenia komputerowe zebrane w trakcie...
-
Metaheurystyki w kolorowaniu grafów
PublikacjaW rozdziale opisano cztery metaheurystyki wykorzystywane w problemie koloro-wania grafów: symulowane wyżarzanie, przeszukiwanie tabu, algorytmy gene-tyczne, algorytmy mrówkowe. Skupiono się głównie na zagadnieniach wykorzys-tania tych metod w badanym problemie.
-
Kolorowanie ścieżek w grafach
PublikacjaZdefiniowano podstawowe pojęcia niezbędne do analizy problemu wyboru i kolo-rowania ścieżek w grafach. Dokonano przeglądu wyników dla grafów ogólnych idla klasycznych rodzin grafów. Omówiono zastosowania praktyczne problemu,zwłaszcza związane ze wspomnianymi już sieciami optycznymi.
-
Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
PublikacjaW 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.
-
Szeregowanie zadań sprzężonych metodą kolorowania grafów
PublikacjaRozważono problem szeregowania zadań sprzężonych na pojedynczym procesorze w obecności ograniczeń kolejnościowych. Zidentyfikowano przypadki wielomianowe dla tego zagadnienia NP-trudnego.
-
O pewnym zastosowaniu uporządkowanego kolorowania grafów
PublikacjaPraca opisuje związki pomiędzy problemami uporządkowanego kolorowania wierzchołków grafów oraz szukania drzewa eliminacji o minimalnej wysokości dla danego grafu. Stąd wynika przydatność tytułowego problemu przy równoległej faktoryzacji macierzy metodą Cholsky´ego.
-
Szeregowanie zadań metodami kolorowania grafów.Monografie 37.
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów w szeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
Modele i metody kolorowania grafów. Część II
PublikacjaNiniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...
-
Modele i metody kolorowania grafów. Część I
PublikacjaNiniejszy artykuł jest pierwszą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano co można kolorować w grafie i jak to można kolorować. Ponieważ kolorowanie we wszystkich odmianach i wariantach jest NP-trudne, podajemy oszacowania na liczbę chromatyczną oraz potencjalne zastosowania...
-
Generowanie sąsiedztwa w algorytmach lokalnych poszukiwań uporządkowanego kolorowania grafów
PublikacjaPrzedstawienie rozwiązań problemów kombinatorycznych w postacipermutacji daje podstawy do konstrukcji algorytmów lokalnychposzukiwań. Uporządkowane pokolorowanie grafu można zapisać w postaci permutacji wierzchołków grafu. Podstawowe operacje prowadzącedo generowania sąsiedztwa rozwiązania to zamiana dwóch elementówlub przesunięcie elementu permutacji. W artykule wskazujemy metodępozwalającą na wykonanie takich operacji w czasie...
-
Wybrane własności problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Zaprezentowano wybrane twierdzenia, oparte w dużej mierze na wynikach badań własnych. Omówiono złożoność obliczeniową problemu routingu chromatycznego i kolorowania ścieżek zarówno...
-
Metaheurystyki dla problemu routingu oraz kolorowania ścieżek w grafie.
PublikacjaReferat dotyczy zagadnienia ścieżkowego kolorowania grafu, które stanowi naturalny model dla problemu routingu i przydziału częstotliwości w czysto optycznej sieci światłowodowej. Zagadnienie optymalizacyjne dla zadanego zbioru zgłoszeń polega na minimalizacji największej użytej wartości koloru ścieżki (tzw. liczby chromatycznej zbioru zgłoszeń). Opisano podstawowe zasady i właściwości ścieżkowego kolorowania grafów. Porównano...
-
Planowanie rozmieszczenia strażników w galeriach sztuki metodą kolorowania grafów
PublikacjaW niniejszym rozdziale zaprezentujemy podejście chromatyczne do wyznaczenialiczby straży w galeriach dowolnego kształtu bez dziur oraz w galeriach or-togonalnych z dziurami, a także bez dziur. Rozważane tu problemy są NP-trud-ne pod względem złożoności obliczeniowej.
-
Cykliczny system otwarty i cyrkularne kolorowanie grafów.
PublikacjaW pracy rozważany jest cykliczny system otwarty - modyfikacja otwartego systemu procesów dedykowanych polegająca na założeniu, że praca jest wykonywana w ruchu ciągłym, czyli kolejne cykle pracy wykonywane są bezpośrednio po sobie. Rozważana jest złożoność obliczeniowa problemów związanych z układaniem harmonogramu w systemach tego typu.
-
Ograniczone (p1, p2,...,pk) kolorowanie wierzchołków grafów.
PublikacjaProblem ograniczonego (p1,...,pk) kolorowania grafów polega na poszukiwaniu odpowiedzi na pytanie, czy istnieje takie pokolorowanie wierzchołków grafu , że krotności użycia poszczególnych barw są równe ustalonym progom p1,...,pk. W ogólnym przypadku problem ten, jako uogólnienie klasycznego kolorowania grafów pozostaje NP-zupełnym. W pracy przedstawiamy wyniki dotyczące ograniczonego kolorowania split grafów, kografów oraz...
-
ASYNCHRONICZNY MULTILATERACYJNY SYSTEM DOZOROWANIA OBSZAROWEGO
PublikacjaW artykule przedstawiono nową metodę lokalizowania samolotów w multilateracyjnych systemach dozorowania obszarowego WAM (Wide Area Multilateration). Metoda ta, nazwana AWAM (Asynchronous Wide Area Multilateration), umożliwia estymację położenia samolotu bez znajomości różnicy w rytmie pracy RTD (Relative Time Difference) pomiędzy stacjami naziemnymi (sensorami). Metoda AWAM znacząco upraszcza proces lokalizowania samolotów w rzeczywistych...
-
Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
PublikacjaArtykuł poświęcony jest szkieletowemu kolorowaniu grafów, które jest matematycznym modelem dla problemu minimalizacji szerokości pasma w sieciach radiowych. Badamy w nim zależność szkieletowej liczby chromatycznej od parametrów zagadnienia. Dowodzimy, że dla dużych wartości parametrów ta zależność jest liniowa.
-
Sprzętowa i programowa realizacja algorytmu szyfrującego AES = Hardware and software implementation of AES algorithm
PublikacjaW artykule przedstawiono sprzętową i programową realizację algorytmu szyfrującego i deszyfrującego AES. Obydwie implementacje zostały zrealizowane z wykorzystaniem platformy Virtex-II i praktycznie zweryfikowane. Jako kryteria do porównania wybrano: zużycie zasobów, przepustowość i zużycie mocy. Wersja sprzętowa charakteryzuje się 190-krotnie większą przepustowością, 80-krotnie mniejszym zużyciem energii na przetworzenie jednego...
-
Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych
PublikacjaW pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.
-
Interference aware bluetooth scatternet (re)configuration algorithm IBLUERA
PublikacjaThis paper presents a new algorithm IBLUEREA, which enables reconfiguration of Bluetooth scatternet to reduce interference. IBLUEREA makes use of the complex model comparing ISM environment efficiency. The mechanism envisages the use of the assessment of the probability of successful (unsuccessful) frame transmission in order to take a decision concerning co-existence of technologies which make use of the same ISM band (here Bluetooth...