Wyniki wyszukiwania dla: KOLOROWANIE KRAWEDZI HIPERGRAFÓW
-
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.
-
Classical coloring of graphs.
PublikacjaRozdział obejmuje klasyczne kolorowanie krawędzi i wierzołków w grafach prostych. Oprócz podstawowych definicji podane zostały najczęściej stosowane metody przybliżone oraz ich właściwości. Dodatkowo rozdział zawiera przegląd znanych benczmarków dla podanych metod w kontekście klasycznego modelu kolorowania.
-
Domination numbers in graphs with removed edge or set of edges
PublikacjaW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesorowych w oknach czasowych
PublikacjaSzeregowanie 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...
-
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...
-
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.
-
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...
-
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...
-
Implementacja w FPGA algorytmu detekcji krawędzi obrazu w czasie rzeczywistym
PublikacjaW artykule przedstawiono projekt architektury oraz implementację układową toru przetwarzania wstępnego obrazu z modułem detekcji krawędzi. Układ został zaimplementowany w FPGA Intel Cyclone. Zrealizowany moduł wykorzystuje pięć wybranych algorytmów wykrywania krawędzi, w tym Robertsa, Sobela i Prewitt.
-
Mixed graph edge coloring
PublikacjaW pracy rozważany jest problem kolorowania krawędzi grafu mieszanego, tj. grafu zawierającego zawiero skierowane, jak i nieskierowane krawędzie. Motywację do badań stanowią zagadnienia komunikacyjne z zakresu szeregowania zadań.
-
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.
-
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.
-
Equitable 4-coloring of cacti and edge-cacti in polynomial time
PublikacjaRozważono problem wyznaczania sprawiedliwej liczby chromatycznej kaktusów i drzew wielokątowych bez trójkątów i krawędzi wiszących. Podano wielomianowy algorytm wyznaczający pokolorowanie optymalne, oparty na paradygmacie programowania dynamicznego. Tym samym znaleziona została kolejna klasa grafów planarnych, dla której kolorowanie sprawiedliwe jawi się jako zagadnienie obliczeniowo łatwe.
-
A note on fast approximate backbone coloring of split graphs with star--like backbones
PublikacjaDla grafu G = (V, E) z wyróżnionym podgrafem H, kolorowanie szkieletowe jest zdefiniowane jako odwzorowanie c spełniające |c(u) - c(v)| > 1 dla każdej krawędzi z E(H) oraz |c(u) - c(v)| > 0 dla każdej krawędzi z E(G). W pracy przedstawiono 1-przybliżony algorytm kolorowania szkieletowego split grafów ze skojarzeniem w szkielecie o złożoności O(|V|) oraz 1-przybliżony algorytm dla split grafów z rozłącznymi gwiazdami w szkielecie.
-
Wybrane zastosowania niestandardowych modeli kolorowania w szeregowniu dwu-procesowych zadań jednostkowych
PublikacjaNiniejsza praca poświęcona jest wykorzystaniu teorii chromatycznej grafów wszeregowaniu. Koncepcja ta polega na przedstawieniu zbioru zadań w postaci krawędzi tzw. grafu konfliktów.
-
O problemie przydziału częstotliwości, kontrastowym kolorowaniu grafów i częściowych k-drzewach
PublikacjaNiniejszy artykuł poświęcony jest złożoności obliczeniowej problemu przydziału częstotliwości. Zawiera dowód tego, że jest on NP-trudny nawet dla grafów interferencji, będących grafami dwudzielnymi, oraz wielomianowy algorytm rozwiązujący ten problem dla grafów interferencji, będących częściowymi k-drzewami.
-
A note on compact and compact circular edge-colorings of graphs
PublikacjaW pracy rozważamy dwa warianty kolorowania krawędzi grafów prostych i ważonych, mianowicie kolorowania zwarte oraz zwarte cyrkularne. Rozważamy relacje pomiędzy nimi. Dowodzimy, że każdy zewnętrznie planarny graf dwudzielny posiada zwarte pokolorowanie krawędziowe oraz, że problem ten dla grafów ogólnych jest NP-zupełny. Podajemy również wielomianowy 1.5-przybliżony algorytm oraz pseudowielomianowy dokładny algorytm zwartego cyrkularnego...
-
Grafowy model macierzy ultrametrycznej i jego zastosowania w filogenezie i t-kolorowaniu
PublikacjaW pracy podano definicję macierzy ultrametrycznej i jej reprezentację grafową. Macierz ta jest wykorzystywana głównie w filogenezie, do budowy drzew ultrametrycznych. W pracy opisano jeden z algorytmów słuzący do konstrukcji takich drzew. Ponadto, omówiono inne możliwe zastosowania modelu grafowego macierzy, tym razem dla problemu przydziału częstotliwości dla nadajników. Zaproponowano również rozwiązanie tego problemu w szczególnym...
-
Weakly connected domination subdivision numbers
PublikacjaLiczba podziału krawędzi dla dominowania słabo spójnego to najmniejsza liczba krawędzi jaką należy podzielić, aby wzrosła liczba dominowania słabo wypukłego. W pracy przedstawione są własności liczby podziału krawędzi dla dominowania słabo spójnego dla różnych grafów.
-
Parallel query processing and edge ranking of graphs
PublikacjaArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
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.
-
A note on mixed tree coloring
PublikacjaZaproponowano liniowy algorytm dla problemu kolorowania mieszanego w drzewach, uzyskując tym samym poprawę w stosunku do algorytmu o złożoności O(n^2) podanego w pracy [P. Hansen, J. Kuplinsky, D. de Werra, Mixed graph colorings, Math. Methods Oper. Res. 45 (1997) 145-160].
-
The complexity of equitable vertex coloring graphs
PublikacjaW artykule podajemy wzory na sprawiedliwą liczbę chromatyczną niektórych produktów grafowych. Ponadto przedstawiamy dwa algorytmy wielomianowe dla sprawiedliwego kolorowania grafów suboptymalną liczba kolorów.
-
Komputerowe stanowisko pomiarowe do analizy dokładności wykonania krawędzi ostrzy narzędzi z wykorzystaniem obrazów z kamer.
PublikacjaW referacie przedstawiono zaprojektowane, wykonane i wdrożone komputerowe stanowisko pomiarowe do analizy dokładności wykonania krawędzi ostrzy narzędzi. Analiza dokładności zrealizowana została na podstawie zarejestrowanych obrazów z kamer. Przedstawiono opisy konstrukcji części mechanicznej stanowiska, układu sterowania, a także ogólną charakterystykę algorytmów sterowania.
-
Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
PublikacjaW artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.
-
The complexity of list ranking of trees
PublikacjaUporzą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...
-
Parallel scheduling by graph ranking
PublikacjaNr 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...
-
Circular colorings of graphs.
PublikacjaRozdział poświęcony jest cyrkularnemu modelowi kolorowania krawędzi. Rozważana jest zarówno wersja wierzchołkowa i krawędziowa. Szczególny nacisk położono na złożoność obliczeniową i zastosowania dla omawianych modeli kolorowania.
-
On greedy graph coloring in the distributed model
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Zaprezentowano nowy probabilistyczny algorytm dający w wyniku pokolorowanie LF. Udowodniono, że jakakolwiek rozproszona implementacja LF wymaga co najmniej D rund, gdzie D jest maksymalnym stopniem wierzchołka w grafie.
-
On the complexity of distributed greedy coloring
PublikacjaW pracy rozważono problem kolorowania grafów przy dodatkowym założeniu, że kolor żadnego wierzchołka nie może zostać zmniejszony bez zmiany kolorów przynajmniej jednego z jego sąsiadów. Przeprowadzone rozważania dotyczyły złożoności obiczeniowej problemu w modelu Liniala obliczeń rozproszonych. Podano ograniczenia dolne i górne złożoności problemu oraz zestawiono problem z innymi pokrewnymi zagadnieniami grafowymi.
-
Cyrkularny indeks chromatyczny grafów kubicznych
PublikacjaW pracy omówiono własności cyrkularnego indeksu chromatycznego grafów kubicznych. Po zdefiniowaniu tego rodzaju kolorowania zbadano, które ze znanych wyników dla klasycznego kolorowania krawędzi grafów kubicznych można przenieść na rozważany model kolorowania. Dodatkowo podano nietrywialne oszacowanie na cyrkularny indeks chromatyczny dla nieskończonej rodziny grafów kubicznych klasy 2.
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublikacjaW pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (open-shop), z kryterium minimalizacji długości harmonogramu oraz sumy czasów zakończenia wszystkich zadań. Zakładając jednostkowe czasy wykonywania operacji można stosować efektywne metody chromatyczne rozwiązywania problemu, poprzez sprowadzenie go do modelu grafowego oraz zastosowanie w nim wybranego modelu kolorowania, które pozwala uzyskać...
-
Interval edge-coloring of graphs.
PublikacjaRozdział poświęcony prezentacji modelu zwartego kolorowania krawędziowego grafów i jego znanych własności. Szczególny nacisk położono na opis klas grafów dających się pokolorować zwarcie w czasie wielomianowym. Omówiono także stratność jako miarę niepodatności grafu na kolorowanie zwarte.
-
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.
-
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...
-
Sum coloring of bipartite graphs with bounded degree.
PublikacjaArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Robert Janczewski dr hab. inż.
Osoby -
Easy and hard instances of arc ranking in directed graphs
PublikacjaArtykuł dotyczy uporządkowanego kolorowania łuków grafów skierowanych. Problem polega na takim przyporządkowaniu liczb łukom digrafu, aby każda skierowana ścieżka łącząca dwa łuki o tej samej liczbie (kolorze) zawierała łuk o kolorze wyższym. Praca podaje liniowy optymalny algorytm dla pewnego szczególnego przypadku, oraz zawiera dowód, iż problem ten jest obliczeniowo trudny dla 3-dzielnych acyklicznych digrafów i stałej liczby...
-
Distributed largest-first algorithm for graph coloring.
PublikacjaW artykule zaprezentowano rozproszony, probabilistyczny algorytm kolorowania grafów. Kolorowanie uzyskane jest optymalne lub prawie optymalne dla takich klas grafów jak koła dwudzielne, gąsienice czy korony. Udowodniono, że algorytm ten działa w czasie O(D^2 log n) rund dla dowolnego grafu n wierzchołkowegoo stopniu maksymalnym D.
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublikacjaW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
On efficient coloring of chordless graphs
PublikacjaArtykuł omawia zagadnienie optymalnego, wielomianowego rozpoznawania i kolorowania grafów bezcięciwowych. Zawiera dowód tego, że takie grafy są zawsze 4-kolorowalne oraz opis wielomianowego algorytmu, który koloruje je minimalną możliwą liczbą kolorów.
-
Optymalne pokolorowania średnicowe dla wybranych klas grafów
PublikacjaW pracy opisano wybrane właściwości szczególnego przypadku radiowego kolorowania grafów, zwanego kolorowaniem średnicowym. Podano zasadę działania algorytmu optymalnego kolorowania średnicowego i oszacowania liczby średnicowej grafu w przypadku ogólnym oraz dla ścieżek i cykli. Korzystając z podanego algorytmu, znaleziono dokładne wartości liczby średnicowej dla ścieżek i cykli niewielkiej długości, co pozwoliło na obalenie wcześniej...
-
Szeregowanie zadań wieloprocesorowych na maszynach dedykowanych w modelu hipergrafowym
PublikacjaOstatnimi 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...
-
The circular chromatic index of some class 2 graphs
PublikacjaW artykule został wyznaczony cyrkularny indeks chromatyczny dla dwóch rodzin grafów klasy 2. Co więcej, podano nie trywialne oszacowania tego parametru dla snarków Isaacsa i Goldberga. Na koniec artykułu rozważana jest złożoność obliczeniowa problemów związanych z cyrkularnym kolorowaniem krawędzi.
-
LICZBA PODZIAŁOWA DLA DOMINOWANIA W GRAFACH
PublikacjaW PRACY ROZWAŻAMY 6 RODZAJÓW ZBIORÓW DOMINUJĄCYCH ORAZ LICZB ZWIĄZANYCH Z TYMI ZBIORAMI: KLASYCZNĄ LICZBĘ DOMINOWANIA, LICZBĘ DOMINOWANIA TOTALNEGO, PARAMI, SŁABO-SPÓJNEGO, 2-DOMINOWANIA I DOMINOWANIA WYPUKŁEGO. W PRACY ROZWAŻAMY WPŁYW TRZECH OPERACJI NA KRAWĘDZIE GRAFU: USUWANIE KRAWĘDZI Z GRAFU, JEDNOKROTNY PODZIAŁ PEWNEJ LICZBY KRAWĘDZI I PODZIAŁ WIELOKROTNY JEDNEJ KRAWĘDZI. BADAMY ZWIĄZKI TYCH OPERACJI Z ROZWAŻANYMI LICZBAMI...
-
Zimnolubna β-D-galaktozydaza Pseudoalteromonas sp. 22b - identyfikacja genu, klonowanie, ekspresja w komórkach Escherichia coli, oczyszczanie i charakterystyka.
Publikacja.
-
Efficient parallel query processing by graph ranking
PublikacjaW artykule analizujemy przybliżony algorytm dla problemu szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym, co znajduje zastosowanie w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie uporządkowanego indeksu chromatycznego drzewa, które prowadzi do uzyskania lepszej funkcji dobroci wspomnianego algorytmu.
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublikacjaProblem 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.
-
Feed forces during cutting of wood on frame sawing machines with narrow-kerf saws.
PublikacjaW pracy przedstawiono wybrane efekty energetyczne procesu przecinania drewna na pilarce ramowej za pomocą cienkich pił. Opisano wyniki badań eksperymentalnych sił posuwu przy zastosowaniu pił o dobrej jakości krawędzi skrawających (piły ostre) oraz pił których krawędzie skrawające były obarczone błędami wykonania w postaci wyszczerbień i wykruszeń krawędzi skrawających. Badania przeprowadzono na pilarce ramowej PRW15M.