Wyszukiwarka
Wyniki wyszukiwania dla: KOLOROWANIE WIERZCHOŁKÓW
-
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.
-
On the complexity of distributed graph coloring with local minimality constraints
PublikacjaArtykuł traktuje o zachłannym kolorowaniu grafów w modelu rozproszonym. Omówiono algorytmy rozproszone, dające w wyniku pokolorowanie spełniające warunki dla pokolorowań sekwencyjnych typu S oraz Largest-First (LF). Udowodniono również, że każda rozproszona implementacja algorytmu S wymaga co najmniej Omega(log n / log log n) rund, a algorytmu LF co najmniej Omega (n^{1/2}) rund, gdzie n oznacza liczbę wierzchołków grafu.
-
Graphs with convex domination number close to their order
PublikacjaW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
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.
-
Compact cyclic edge-colorings of graphs
PublikacjaArtykuł jest poświęcony modelowi zwartego cyklicznego kolorowania krawędzi grafów. Ten wariant kolorowania jest stosowany w modelowaniu uszeregowań w systemach produkcyjnych, w których proces produkcyjny ma charakter cykliczny. W pracy podano konstrukcje grafów, które nie zezwalają na istnienie pokolorowania w rozważanym modelu. Wykazano także kilka własności teoretycznych, takich jak ograniczenia górne na liczbę kolorów w optymalnym...
-
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...
-
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.
-
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.
-
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].
-
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 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublikacjaWe consider the CHROMATIC SUM PROBLEM on bipartite graphs which appears to be much harder than the classical CHROMATIC NUMBER PROBLEM. We prove that the CHROMATIC SUM PROBLEM is NP-complete on planar bipartite graphs with Delta less than or equal to 5, but polynomial on bipartite graphs with Delta less than or equal to 3, for which we construct an O(n(2))-time algorithm. Hence, we tighten the borderline of intractability for this...
-
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.
-
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...
-
Wpływ parametrów geometrycznych próbki stalowej na uzyskaną wartość wskaźnika krytycznego rozwarcia wierzchołka szczeliny CTOD w badaniach odporności na pękanie
PublikacjaW pracy podjęto problem określania ciągliwości materiału metodami mechaniki pękania, jako jednego z częściej wymaganych kryteriów dla konstrukcji okrętowych i oceanotechnicznych. Na podstawie rozważań i modeli numerycznych, studiowano problem wpływu parametrów geometrycznych próbki na wynik znormalizowanej próby określania krytycznego rozwarcia wierzchołka szczeliny - CTOD. W pierwszej części pracy dokonano przeglądu metod...
-
Edge ranking and searching in partial orders
PublikacjaArtykuł jest poświęcony problemowi konstrukcji optymalnej (wymagającej minimalnej ilości porównań/zapytań) strategii wyszukiwania elementu w częściowym porządku. W pracy wskazano związki pomiędzy tym problemem oraz uporządkowanym kolorowaniem krawędzi grafów, co implikuje liniowy algorytm dla częściowych porządków o strukturze drzewa. Pokazano również, że znalezienie optymalnej strategii jest problemem obliczeniowo trudnym dla...
-
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.
-
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.
-
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.
-
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.
-
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.
-
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.
-
Cholesky factorization of matrices in parallel and ranking of graphs.
PublikacjaUporządkowane kolorowanie znajduje zastosowanie przy równoległej faktoryzacji macierzy metodą Cholesky'ego. Praca zawiera opis tego zastosowania. Podano także algorytmy optymalnego uporządkowanego kolorowania krawędzi pewnych klas grafów: grafów pełnych dwudzielnych oraz powstałych z pełnych dwudzielnych przez usunięcie O(log n) krawędzi.
-
Równowaga strategiczna dla zbiorów defensywnych w drzewach
PublikacjaW pracy rozważany jest problem defensywnej równowagi strategicznej dla zbiorów defensywnych w drzewach (spójnych grafach acyklicznych), który polega na znalezieniu dwóch rozłącznych globalnych zbiorów defensywnych. Zagadnienie to znajduje zastosowanie w modelo- waniu problemów komunikacyjnych w sieciach. Dla danego grafu G podzbiór jego wierzchołków S jest zbiorem defensywnym, jeśli dla każdego wierzchołka v należącego do S spełniony...
-
Robert Janczewski dr hab. inż.
Osoby -
Hipergrafowy model szeregowania w rozrzedzonych systemach zadań wieloprocesorowych
PublikacjaHipergrafem 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. W tym artykule będziemy mówić o kolorowaniu krawędzi hiperdrzew. Pokażemy jaki jest indeks chromatyczny dla tej klasy hipergrafów oraz jaki jest sumacyjny indeks chromatyczny dla hiperdrzew prostych. Zademonstrujemy także wielomianowe algorytmy szukające...
-
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.
-
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.
-
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...
-
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...
-
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.
-
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...
-
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.
-
Marek Kubale prof. dr hab. inż.
OsobyDetails concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...
-
Lower bound on the weakly connected domination number of a tree
PublikacjaPraca dotyczy dolnego ograniczenia liczby dominowania słabo spójnego w drzewach (ograniczenie ze względu na ilość wierzchołków i ilość wierzchołków końcowych w drzewie).
-
Drawing maps with advice
PublikacjaRozważamy następujący problem obliczeniowy. Agent zostaje umieszczony w wierzchołku nieznanego mu grafu. Wierzchołki grafu są nierozróżnialne, natomiast krawędzie posiadają numery portów. Zadaniem agenta jest wyznaczenie mapy, tzn. obliczenie izomorficznej kopii grafu, lub obliczenie dowolnego drzewa spinającego grafu. Bez dodatkowej informacji zadań tych nie można wykonać. W artykule wyznaczamy oszacowania na minimalną liczbę...
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013024871]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013025741]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013023871]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013025791]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013025971]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013028101]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013024861]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013027891]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [131063001302811]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.
-
Acinar adenocarcinoma of prostate - Male, 69 - Tissue image [1310630013027271]
Dane BadawczeThis is the histopathological image of PROSTATE GLAND tissue sample obtained in Medical University Gdańsk and deposited in ZMDL-GUMED. The sample image was taken using: Pannoramic 250 3DHistech slide scanner (20x magnification) and saved to DICOM format.