Publications
Filters
total: 517
Catalog Publications
Year 2009
-
Preface of guest editors
PublicationA special issue of Discussiones Mathematice Graph Theory (DMGT) is dedicated to selected papers presented at the 12th Workshop on Graph Theory: Colourings, Independence and Domination (CID) held on 16-21 September 2007 in Karpacz, Poland. It continues a series of international workshops: 1993-1997 in Lubiatów, 1998-2001 in Gronów, 2003 and 2005 in Karpacz. About 70 participants formed the audience of six invited lectures and 68...
-
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
-
Synchronization helps robots to detect black holes in directed graphs
PublicationPraca zawiera nowe wyniki dla problemu poszukiwania czarnej dziury w grafie skierowanym przez zbiór agentów. Czarna dziura jest węzłem niszczącym wszystkich wchodzącej do niej agentów. Pokazano, że w przypadku, gdy stopień wejściowy czarnej dziury wynosi D, do przeszukania grafu skierowanego w modelu synchronicznym wystarcza O(D 2^D) agentów. Wartość ta jest bliska znanemu z literatury oszacowaniu dolnemu Omega (2^D). W pracy pokazano...
-
Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi
PublicationW 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ń 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...
-
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...
-
Turbine stage design aided by artificial intelligence methods
PublicationZaproponowano ogólny, wydajny system wspomagania projektowania palisad , stopni i grupy stopni turbinowych. Zastosowane algorytmy wykorzystują algorytmy genetyczne, sieci neuronowe i obliczenia równoległe. Uzyskane rozwiązania projektowe są wysoko zoptymalizowane pod względem sprawności, a czas ich uzyskania jest o kilka rzędów wielkości mniejszy, niż przy zastosowaniu obliczeń CFD.
-
Universal Augmentation Schemes for Network Navigability
PublicationRozważano problem uzupełniania grafu (reprezentującego np. sieci społeczne) poprzez dodanie w każdym węźle jednego dodatkowego skierowanego połączenia (długodystansowego). Dokładniej, dla każdego węzła definiuje się listę prawdopodobieństw istnienia połączenia wychodzącego z danego węzła do wszystkich pozostałych węzłów; wartości tych prawdopodobieństw muszą sumować się do jedności. Routing zachłanny w takiej sieci polega na przekazywaniu...
-
What Can Be Observed Locally? Round based models for quantum distributed computing
PublicationW pracy rozważono zagadnienie lokalności w kontekście informacji kwantowej w obliczeniach rozproszonych. Rozważono dwa kwantowe rozszerzenia modelu LOCAL Liniala, otrzymane poprzez: (1) inicjalizację systemu w kwantowym stanie splątanym, (2) zastosowanie kwantowych kanałów komunikacyjnych. Dla obydwu typów rozszerzeń zaproponowano przykłady problemów, których złożoność rundowa ulega redukcji w porównaniu do oryginalnego modelu...
Year 2008
-
A note on compact and compact circular edge-colorings of graphs
PublicationW 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...
-
A note on mixed tree coloring
PublicationZaproponowano 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].
-
Application of an online judge & contester system in academic tuition
PublicationPraca zawiera opis systemu typu ''Online judge & contester'' o nazwie SPOJ, wykorzystywanego do zdalnej nauki programowania. Został on pomyślnie wdrożony w nauczaniu informatyki na Politechnice Gdańskiej. Omówiono zasadę działania i mechanizmy bezpieczeństwa systemu SPOJ. Przedstawiono wnioski z doświadczeń przy stosowaniu tego typu systemów w nauczaniu na etapie studiów 1. i 2. stopnia w ciągu ostatnich czterech lat.
-
Compact cyclic edge-colorings of graphs
PublicationArtykuł 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...
-
Comparing phylogenetic trees using a minimum weight perfect matching
PublicationA phylogenetic tree represents historical evolutionary relationshipbetween different species or organisms. There are various methods for reconstructing phylogenetic trees.Applying those techniques usually results in different treesfor the same input data. An important problem is to determinehow distant two trees reconstructed in such a wayare from each other. Comparing phylogenetic trees is alsouseful in mining phylogenetic information...
-
Computer experiments with a parallel clonal selection algorithm for the graph coloring problem
PublicationArtificial immune systems (AIS) are algorithms that are based on the structure and mechanisms of the vertebrate immune system. Clonal selection is a process that allows lymphocytes to launch a quick response to known pathogens and to adapt to new, previously unencountered ones. This paper presents a parallel island model algorithm based on the clonal selection principles for solving the Graph Coloring Problem. The performance of...
-
Cost minimisation in unbounded multi-interface networks
PublicationW pracy badano problem odłączania niektórych urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń przy jednoczesnej minimalizacji zużycia energii. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne dla wariantu, w którym liczba interfejsów komunikacyjnych jest potencjalnie nieograniczona...
-
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.
-
Edge ranking and searching in partial orders
PublicationArtykuł 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...
-
Inferring perfect phylogenies with restrictions on character state transitions
PublicationZnana z klasycznej literatury metoda rekonstrukcji drzewa filogenetycznego zbioru gatunków na podstawie ich cech analizowanych w modelu doskonałej filogenezy często okazuje się niewystarczająca ze względu na założenia tego modelu, zmuszające do pominięcia znanych biologom informacji. W pracy definiujemy rozszerzenie umożliwiając wprowadzenie dla każdej cechy grafu skierowanego dopuszczalnych przejść ewolucyjnych pomiędzy jej stanami....
-
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++....