Search
Search results for: KOLOROWANIE KRAWEDZI HIPERGRAFU
-
Szeregowanie zadań wieloprocesorowych na maszynach dedykowanych w modelu hipergrafowym
PublicationOstatnimi 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...
-
On the complexity of distributed graph coloring with local minimality constraints
PublicationArtykuł 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.
-
Derandomizing random walks in undirected graphs using locally fair exploration strategies
PublicationW pracy rozważono problem eksploracji anonimowego nieskierowanego grafu przez bezpamięciowego robota. Zaprojektowane strategie eksploracji cechują się własnością lokalnej sprawiedliwości, tj. kolejne krawędzie trawersowane przez robota wybierane są na podstawie lokalnych informacji tak, aby zapewnić równomierne wykorzystanie krawędzi w sensie pewnego kryterium. Okazuje się, że odpowiedni dobór kryterium jest kluczowy do zapewnienia...
-
Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych
PublicationUmieszczenie grafu w grafie jest odwzorowaniem pomiędzy parą grafów. Graf umieszczany reprezentuje sieć komunikujących się ze sobą zadań, natomiast graf docelowy dostępną architekturę wykonania tych zadań. Problem polega na takim odwzorowaniu wierzchołków i krawędzi, aby zminimalizować koszty wynikające z potrzeby użycia zastępczych ścieżek w grafie docelowym. W klasycznym modelu przyjmuje się, że oba grafy są proste i ich krawędzie...
-
Badania stanu technicznego ścianek szczelnych strony południowej i północnej komory południowej śluzy Dzierżno
PublicationPrace dotyczyły badań nieniszczących łączników (zamków) Paine`a oraz ścianek szczelnych. Ściany boczne komory południowej śluzy Dzierżno zbudowane są ze stalowych pasów blachy o grubości około 16mm i długości 22m połączonych ze sobą wzdłuż dłuższej krawędzi za pomocą zamków Peine`a. System ten umożliwia uzyskanie szczelnego połączenia na całej długości ścianki. Zaawansowany proces korozji spowodował rozszczelnienie połączenia...
-
Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych
PublicationProblem 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.
-
Jerzy Konorski dr hab. inż.
PeopleJerzy Konorski received his M. Sc. degree in telecommunications from Gdansk University of Technology, Poland, and his Ph. D. degree in computer science from the Polish Academy of Sciences, Warsaw, Poland. In 2007, he defended his D. Sc. thesis at the Faculty of Electronics, Telecommunications and Informatics, Gdansk University of Technology. He has authored over 150 papers, led scientific projects funded by the European Union,...
-
Identification, cloning, expression, and characterizationof a highly thermostable single-stranded-DNA-binding protein (SSB) from Deinococcus murrayi
PublicationZidentyfikowano i scharakteryzowano białko SSB-podobne, pochodzące z Deinococcus murrayi (DmuSSB). Otrzymany w reakcji PCR fragment zawierający kompletny gen ssb sklonowano w systemie ekspresyjnym Escherichia coli. Gen składa się z 826 nt, kodujących 276 reszt aminokwasowych z wyliczoną teoretycznie masą cząsteczkową monomeru równą 30,14 kDa. DmuSSB zawiera dwie domeny wiążące jednoniciowe DNA OBna monomer I funkcjonuje jako homodimer....
-
Strong weakly connected domination subdivisible graphs
PublicationArtykuł dotyczy wpływu podziału krawędzi na liczbę dominowania słabo spójnego. Charakteryzujemy grafy dla których podział dowolnej krawędzi zmienia liczbę dominowania słabo spójnego oraz grafy dla których podział dowolnych dwóch krawędzi powoduje zmianę liczby dominowania słabo spójnego.
-
A new B-D-galactosidase with a low temperature optimum isolated from the Antarctic Arthrobacter sp. 20B: gene cloning, purification and characterization.
PublicationA psychrotrophic bacterium producing a coldadaptedB-galactosidase upon growth at low temperatureswas classiWed as Arthrobacter sp. 20B. A genomic DNAlibrary of strain 20B introduced into Escherichia coliTOP10F' and screening on X-Gal (5-bromo-4-chloro-3-indolyl-B-D-galactopyranoside)-containing agar plates ledto the isolation of B-galactosidase gene. The B-galactosidasegene (bgaS) encoding a protein of 1,053 amino acids,with a...
-
Some results on trading model in a consensus list coloring
PublicationKonsensusowy 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...
-
Harmonions Coloring of Graphs.
PublicationProblem kolorowania grafów jest motywowany radionawigacją lotniczą, kompresją obrazów i in. W rozdziale podano podstawowe fakty dotyczące tego modelu kolorowania, a wsród nich dolne i górne oszacowania na liczbę harmoniczną i algorytm o złożoności 0 (mm3) dający bardzo dobre pokolorowania przybliżone.
-
The complexity of the L(p,q)-labeling problem for bipartite planar graphs of small degree
PublicationW pracy pokazano, że problem L(p,q)-kolorowania przy użyciu ''t'' kolorów jest NP-zupełny nawet w wersji ograniczonej do grafów planarnych dwudzielnych małego stopnia, nawet dla stosunkowo niewielkich wartości ''t''. Jako wniosek z uzyskanych wyników stwierdzono, że problem L(2,1)-kolorowania grafów planarnych przy użyciu 4 kolorów jest NP-zupełny, a także że problem L(p,q)-kolorowania grafów o maksymalnym stopniu 4 jest NP-zupełny...
-
T-coloring of graphs.
PublicationNiniejszy rozdział omawia kontrastowe kolorowanie grafów. Podana została jego definicja i podstawowe własności, zastosowania oraz złożoność obliczeniowa problemów rozważanych w ramach tej dziedziny.
-
Koala graph coloring library: an open graph coloring library for real-world applications
PublicationPomimo intensywnej pracy naukowej na polu kolorowania grafów, nie jest znana kompletna i dedykowana biblioteka programistyczna. Celem artykułu jest zaproponowanie architektury takiej biblioteki. Celem jest spełnienie oczekiwań wypływających z rzeczywistych zastosowań, w szczególności spełnienie potrzeb wydajnościowych. Zaimplementowano szereg algorytmów cheurystycznego kolorowania grafów. Przyjętym językiem programowania jest C++....
-
The complexity of the T-coloring problem for graphs with small degree.
PublicationW pracy ustalono złożoność obliczeniową problemu optymalnego kolorowania grafów o ustalonym stopniu.
-
An experimental study of distributed algorithms for graph coloring.
PublicationW pracy podano algorytm rozproszonego kolorowania grafówi porównano ze znanym wcześniej algorytmem.
-
Rank Coloring of Graphs.
PublicationRozdział jest poświęcony uporządkowanemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Sum Coloring of Graphs.
PublicationRozdział jest poświęcony sumacyjnemu kolorowaniu grafów. Przedstawiono jego podstawowe własności oraz zastosowania praktyczne.
-
Duże rozgłoszeniowe pola Closa
PublicationW pracy pokazano nowe podejście do blokowalności dużych rozgłoszeniowych pól Closa. Przedstawione zostały także dowody na blokowalność pola C(n,r_1,n^2-1,n,r_2) oraz pola C(n,r_1,n^2,n,r_2), w których użyto ekstremalną teorię grafów i hipergrafów.
-
A 27/26-approximation algorithm for the chromatic sum coloring of bipartitegraphs
PublicationWe 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...
-
Zdzisław Kowalczuk prof. dr hab. inż.
PeopleZdzislaw Kowalczuk received his M.Sc. degree in 1978 and Ph.D. degree in 1986, both in Automatic Control from Technical University of Gdańsk (TUG), Gdańsk, Poland. In 1993 he received his D.Sc. degree (Dr Habilitus) in Automatic Control from Silesian Technical University, Gliwice, Poland, and the title of Professor from the President of Poland in 2003. Since 1978 he has been with Faculty of Electronics, Telecommunications and Informatics...
-
Paired bondage in trees
PublicationW pracy zdefiniowano pojęcie liczby zniewolenia parami jako moc najmniejszego zbioru krawędzi, którego usunięcie z grafu spowoduje wzrost liczby dominowania parami. W szczególności scharakteryzowane są wszystkie drzewa, w których liczba zniewolenia wynosi 0, czyli takie, w których usunięcie dowolnego podzbioru krawędzi nie zwiększy liczby dominowania parami.
-
Robustness of the Rotor-router Mechanism
PublicationW pracy rozważano model eksploracji grafu nieskierowanego przez pojedynczego agenta, w którym sterowanie agentem odbywa się zgodnie z zasadą ''rotor-router'' (inaczej: ''Propp machine''). Przeanalizowano czas stabilizacji agenta do trajektorii w postaci cyklu Eulera w przypadku wystąpienia zaburzeń w grafie: usunięcie krawędzi, dodanie krawędzi, lokalna zamiana portów
-
Antypodalna radiowa liczba chromatyczna grafu.
PublicationOpisane zostały podstawowe zasady i właściwości antypodalnego kolorowania grafów. Zebrano publikowane w literaturze przedmiotu twierdzenia i uzupełniono wnioskami wynikającymi z własnych badań.
-
Interval wavelength assignment in all-optical star networks
PublicationArtykuł omawia zwarte końcówkowe kolorowanie grafów, które jest matematycznym modelem dla problemu przydziału częstotliwości w sieciach optycznych. W artykule przedstawiono wielomianowe algorytmy wyznaczania zwartej końcówkowej liczby chromatycznej dla pełnych grafów k-dzielnych, drzew i podkubicznych grafów dwudzielnych.
-
Dominowanie w grafach
PublicationW pracy rozważanych jest pięć liczb dominowania: klasyczna liczba dominowania, liczba dominowania spójnego, liczba dominowania słabo spójnego, liczba dominowania słabo wypukłego i liczba dominowania wypukłego. Rozważane są pewne ograniczenia na liczby dominowania, równości między poszczególnymi liczbami, wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania i NP-zupełność problemów dominowania.
-
Equitable vertex coloring of graphs
PublicationW pracy podajemy wartości sprawiedliwej liczby chromatycznej dla niektórych klas grafów. Podajemy również dwa algorytmy heurystyczne dla sprawiedliwego kolorowania grafów z suboptymalna liczba koloru.
-
Wpływ redukcji grubości elementu betonowego na nośność kotew metalowych w betonie
PublicationGrubość elementu betonowego przyjęta z warunków wykonawczych, bez negatywnego wpływu naroży i krawędzi, jest wystarczająca do osiągnięcia nośności charakterystycznej jak dla elementu o standardowej wysokości minimalnej. Nie ma tu obawy o przedwczesne zniszczenie betonu przez rozłupanie. Aby uzyskać wymaganą nośność z uwzględnieniem wzajemnego rozstawu łączników i wpływem obecności krawędzi elementu należy przeprowadzić dodatkowe...
-
Designing optimal and safe control strategies for time-varying dynamical systems
PublicationPublikacja opisuje metodę projektowania optymalnej trajektorii punktu pracy w czasoprzestrzeni stanów przy wykorzystaniu algorytmów optymalizacji grafowej. Zakłada się deterministyczny charakter zmian dynamiki rozpatrywanego procesu. Przestrzeń robocza, będąca ograniczonym podzbiorem czasoprzestrzeni stanów, jest dzielona na zbiór segmentów, którym przypisywane są wielkości reprezentujące właściwości dynamiki własnej w obrębie...
-
Miernictwo i systemy pomiarowe W/L, IMM, sem. 04, letni 21/22 (M:31677W0)
e-Learning CoursesPodstawowe pojęcia z metrologii. Metody, błędy i niepewność pomiarów. Tolerowanie i pasowania długości i kątów. Metody analizy wymiarowej. Zasady zamienności części maszyn. Dokładność wykonania przedmiotów. Elementy specyfikacji geometrii wyrobów, tolerowanie kształtu, kierunku i położenia. Charakterystyka struktury geometrycznej powierzchni przedmiotów. Zasady tolerowania geometrycznego. Wzorce i przyrządy pomiarowe.
-
Metrologia i systemy pomiarowe, W/L/C, MiBM NST, sem. 04, letni 21/22 (M:31917W0)
e-Learning CoursesPodstawowe pojęcia z metrologii. Metody, błędy i niepewność pomiarów. Tolerowanie i pasowania długości i kątów. Metody analizy wymiarowej. Zasady zamienności części maszyn. Dokładność wykonania przedmiotów. Elementy specyfikacji geometrii wyrobów, tolerowanie kształtu, kierunku i położenia. Charakterystyka struktury geometrycznej powierzchni przedmiotów. Zasady tolerowania geometrycznego. Wzorce i przyrządy pomiarowe.
-
Metrologia i systemy pomiarowe , W/L/C, ZiIP, sem. 02, letni 21/22 (PG_00055050)
e-Learning CoursesPodstawowe pojęcia z metrologii. Metody, błędy i niepewność pomiarów. Tolerowanie i pasowania długości i kątów. Metody analizy wymiarowej. Zasady zamienności części maszyn. Dokładność wykonania przedmiotów. Elementy specyfikacji geometrii wyrobów, tolerowanie kształtu, kierunku i położenia. Charakterystyka struktury geometrycznej powierzchni przedmiotów. Zasady tolerowania geometrycznego. Wzorce i przyrządy pomiarowe.
-
Consensus models: Computational complexity aspects in modern approaches to the list coloring problem
PublicationArtykuł poświęcony jest nowym modelom konsensusowego kolorowania grafów. Artykuł zawiera omówienie trzech takich modeli, analizę ich złożoności obliczeniowej oraz wielomianowy algorytm dla częściowych k-drzew, dla tzw. modelu addytywnego.
-
Metrologia i systemy pomiarowe , W/L/C, MiBM, sem. 02, letni 21/22 (PG_00055375)
e-Learning CoursesPodstawowe pojęcia z metrologii. Metody, błędy i niepewność pomiarów. Tolerowanie i pasowania długości i kątów. Metody analizy wymiarowej. Zasady zamienności części maszyn. Dokładność wykonania przedmiotów. Elementy specyfikacji geometrii wyrobów, tolerowanie kształtu, kierunku i położenia. Charakterystyka struktury geometrycznej powierzchni przedmiotów. Zasady tolerowania geometrycznego. Zaawansowane metody pomiarowe (WMP,...)....
-
Wpływ konstrukcji przestrzeni międzyklockowej na charakterystyki wzdłużnego łożyska ślizgowego
PublicationSmarowanie zanurzeniowe jest tradycyjnym sposobem smarowania dużych wzdłużnych łożysk ślizgowych. W chwili obecnej wymagania stawiane nowym konstrukcjom łożysk ślizgowych to zwiększanie nośności łożyska, które następuje m. in. po obniżeniu temperatury maksymalnej w filmie smarowym, co można uzyskać poprzez skuteczne dostarczanie zimnego oleju zasilającego wprost do strefy wlotowej filmu olejowego. Jednym z takich rozwiązań konstrukcyjnych,...
-
Path Coloring and Routing in Graphs.
PublicationW rozdziale omówione zostały problemy kolorowania ścieżek i routingu w grafach. Podano podstawowe definicje związane z tymi problemami, znane wyniki wraz z dyskusją złożoności obliczeniowej dla grafów ogólnych i dla kilku podstawowych klas grafów oraz zastosowania.
-
Skuteczność zabezpieczenia przeciw pożarowego zbiorników stalowych na paliwa płynne
PublicationPodano mechanizm niszczenia konstrukcji zbiorników stalowych podczas pożaru. Wskazano, że skuteczniejsza jest instalacja gaśnicza umieszczona na dnie zbiornika a nie na górnej krawędzi płaszcza
-
Skuteczność zabezpieczeń przeciwpożarowych zbiorników na paliwa płynne
PublicationPodano mechanizm niszczenia konstrukcji zbiornika stalowego podczas pożaru. Wskazano, że skuteczniejsza jest instalacja gaśnicza umieszczona na dnie zbiornika a nie na górnej krawędzi płaszcza
-
M-Split Estimation in Laser Scanning Data Modeling
PublicationPublikacja traktuje o wykorzystaniu estymacji M-Split do modelowania danych pozyskanych w wyniku skaningu laserowego. Autorzy prezentują rozwiązanie w oparciu o detekcję krawędzi dwóch płaszczyzn.
-
Badania wybranych efektów docierania powierzchni płaskich elementów stalowych
PublicationPrzedstawiono wyniki badań stanu powierzchni elementów płaskich docieranych w układzie jednotarczowym. Analizowano chropowatość powierzchni oraz strefę wejścia mikroziaren w procesie zaokrąglenia krawędzi docieranych elementów i zużycie ścierniwa.
-
Zastosowania trójkątnych płytek w grafice komputerowej
PublicationPraca opisuje metody pokrywania trójkątnymi płytkami dowolnych powierzchni trójwymiarowych reprezentowanych przez siatki trójkątne. Omówione są znane metody konstruowania i układania trójkątnych płytek oraz ich optymalizacja algorytmami kolorowania grafów. Zaproponowana jest ulepszona hybrydowa metoda, umożliwiająca pokrycie dowolnej powierzchni wzorem, który wymaga kierunkowego uporządkowania.
-
Numerical analysis of laminated shells under in-plane axial compression
PublicationW pracy analizowana jest stateczność powłoki warstwowej poddanej osiowemu ściskaniu. Badany jest wpływ wariantów uwarstwienia oraz warunków podparcia krawędzi obciążonej na zachowanie konstrukcji. Wyniki numeryczne porównano z eksperymentem.
-
Analiza przepływu oleju przez rowek smarowy wzdłużnego łożyska ślizgowego = Analysis of the lubricant flow through the hydrodynamic thrust bearings groove
PublicationSmarowanie zanurzeniowe jest tradycyjnym sposobem smarowania wzdłużnych łożysk ślizgowych. Jednak rozwiązanie to wykazuje umiarkowaną skuteczność w zapewnieniu optymalnie niskich temperatur w filmie smarowym a ponadto jest przyczyną strat mocy związanych z mieszaniem oleju w obudowie łożyska, co jest szczególnie widoczne w łożyskach szybkoobrotowych. Wymagania stawiane nowym konstrukcjom łożysk ślizgowych to zwiększanie nośności...
-
Analiza przepływu oleju przez rowek smarowy wzdłużnego łożyska ślizgowego z wykorzystaniem komputerowej dynamiki płynów (CFD) = Analysis of the lubricant flow through the hydrodynamic thrust bearings groove with the use of computational fluid dynamic
PublicationSmarowanie zanurzeniowe jest tradycyjnym sposobem smarowania wzdłużnych łożysk ślizgowych. Jednak rozwiązanie to wykazuje umiarkowaną skuteczność w zapewnieniu optymalnie niskich temperatur w filmie smarowym a ponadto jest przyczyną strat mocy związanych z mieszaniem oleju w obudowie łożyska, co jest szczególnie widoczne w łożyskach szybkoobrotowych. Obecnie wymagania stawiane nowym konstrukcjom łożysk ślizgowych to zwiększanie...
-
Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.
PublicationW pracy rozważono problem kolorowania grafów mieszanych, opisujący zagadnienie szeregowania zadań, w którym zależności czasowe zadań mają charakter częściowego porządku lub wzajemnego wykluczania. Dla przypadku, w którym graf zależności jest szeregowo-równoległy, podano algorytm rozwiązujący problem optymalnie w czasie $O(n^3.376 * log n)$.
-
Approximation strategies for routing edge disjoint paths in complete graphs
PublicationPraca dotyczy problemu ścieżek krawędziowo rozłącznych w nieskierowanych grafach pełnych, dla którego podano nowe algorytmy przybliżone: 3.75-przybliżony (model off-line) i 6.47-przybliżony (model on-line). Stosując podobną metodologię, uzyskano algorytm 4.5-przybliżony (off-line) i 6-przybliżony (on-line) dla problemu routingu i kolorowania ścieżek w grafach pełnych.
-
Energy optimisation in resilient self-stabilizing processes
PublicationW 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.
-
Damage location in beam and plate structures by wavelet analysis of experimentally determined mode shapes
PublicationArtykuł dotyczy zastosowania analizy falkowej do lokalizacji uszkodzeń w konstrukcjach belkowych i płytowych. Wykonano testy dynamiczne belki wspornikowej i płyty utwierdzonej wzdłuż jednej z krawędzi. Lokalizację defektu otrzymano za pomocą transformaty falkowej eksperymentalnie wyznaczonych postaci drgań.
-
Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych
PublicationPokazano, że pewien problem transportu produktów chemicznych może być sprowadzony do problemu szeregowania identycznych zadań kompatybilnych na wsadowych maszynach jednorodnych i rozwiązany metodami kolorowania grafów. Ponieważ problem ten jest NP-trudny, zbadano przypadki szczególne, które dają się rozwiązać w czasie kwadratowym. Rozważania ogólne są wsparte doświadczeniami komputerowymi zebranymi w trakcie implementacji wybranych...