Katedra Algorytmów i Modelowania Systemów - Jednostki Administracyjne - MOST Wiedzy

Wyszukiwarka

Katedra Algorytmów i Modelowania Systemów

Filtry

wszystkich: 396
  • Kategoria

  • Typ

  • Rok

  • Opcje

Katalog

  • 2009

  • Greedy T-colorings of graphs

    Treścią artykułu są pokolorowania kontrastowe wygenerowane przez algorytm zachłanny. Zbadane zostały ich własności, obejmujące liczbę kolororów, rozpiętość i rozpiętość krawędziową.
    • Pełny tekst w serwisie zewnętrznym
  • Gwarantowanie bezpieczeństwa w systemie z połączeniami awaryjnymi

    Rozważamy zapewnianie bezpieczeństwa przed zewnętrznym intruzem w systemie o topologii drzewa, w którym wprowadzono dodatkowe połączenia awaryjne. Grupa mobilnych autonomicznych agentów musi przechwycić intruza, niezależnie od przyjętej przez niego strategii unikania. W literaturze problem ten jest modelowany jako przeszukiwanie grafów. W pracy zawężamy dotychczasowe oszacowanie na liczbę przeszukiwawczą kaktusów podkubicznych,...
  • Maximum vertex occupation time and inert fugitive: recontamination does help [online]

    Rozważamy problem przeszukania danego grafu prostego G w celu przechwycenia niewidocznego i leniwego uciekiniera. Parametrem optymalizacyjnym, który minimalizujemy jest maksymalny czas (liczba tur strategii przeszukiwania), podczas których wierzchołek może być strzeżony (okupowany przez strażnika). Strategia monotoniczna to taka, która nie dopuszcza sytuacji, w której uciekinier dociera do wierzchołka, który wcześniej został oczyszczony....
    • Pełny tekst w serwisie zewnętrznym
  • Minimum vertex ranking spanning tree problem for chordal and proper interval graphs

    W pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
    • Pełny tekst w serwisie zewnętrznym
  • Mixed graph edge coloring

    H. Furmańczyk, A. Kosowski, B. Ries, P. Żyliński - DISCRETE MATHEMATICS - 2009
    W 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ń.
    • Pełny tekst w serwisie zewnętrznym
  • On efficient coloring of chordless graphs

    Artykuł 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.
    • Pełny tekst w serwisie zewnętrznym
  • On the complexity of distributed graph coloring with local minimality constraints

    C. Gavoille, R. Klasing, A. Kosowski, Ł. Kuszner, A. Navarra - NETWORKS - 2009
    Artykuł 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.
    • Pełny tekst w serwisie zewnętrznym
  • Preface of guest editors

    P. Borowiecki, E. Sidorowicz, D. Michalak - Discussiones Mathematicae Graph Theory - 2009
    A 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...
    • Pełny tekst w serwisie zewnętrznym
  • Robustness of the Rotor-router Mechanism

    E. Bampas, L. Gąsieniec, R. Klasing, A. Kosowski, T. Radzik - 2009
    W 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
    • Pełny tekst w serwisie zewnętrznym
  • Synchronization helps robots to detect black holes in directed graphs

    K. Kosowski, A. Navarra, C. Pinotti - 2009
    Praca 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...
    • Pełny tekst w serwisie zewnętrznym
  • Szeregowanie zadań wieloprocesorowych metodą kolorowania hiperkrawędzi

    W 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

    P. Obszarski - 2009
    Ostatnimi 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

    W 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...
    • Pełny tekst w serwisie zewnętrznym
  • Turbine stage design aided by artificial intelligence methods

    Zaproponowano 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.
    • Pełny tekst w serwisie zewnętrznym
  • Universal Augmentation Schemes for Network Navigability

    P. Fraigniaud, C. Gavoille, A. Kosowski, E. Lebhar, Z. Lotker - THEORETICAL COMPUTER SCIENCE - 2009
    Rozważ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...
    • Pełny tekst w serwisie zewnętrznym
  • What Can Be Observed Locally? Round based models for quantum distributed computing

    C. Gavoille, A. Kosowski, M. Markiewicz - 2009
    W 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...
    • Pełny tekst w serwisie zewnętrznym
  • 2008

  • A note on compact and compact circular edge-colorings of graphs

    W 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...
    • Pełny tekst w serwisie zewnętrznym
  • A note on mixed tree coloring

    H. Furmańczyk, A. Kosowski, P. Żyliński - INFORMATION PROCESSING LETTERS - 2008
    Zaproponowano 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].
    • Pełny tekst w serwisie zewnętrznym
  • Application of an online judge & contester system in academic tuition

    Praca 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

    Artykuł 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...
    • Pełny tekst w serwisie zewnętrznym
  • Comparing phylogenetic trees using a minimum weight perfect matching

    A 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...
    • Pełny tekst w serwisie zewnętrznym
  • Computer experiments with a parallel clonal selection algorithm for the graph coloring problem

    Artificial 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...
    • Pełny tekst w serwisie zewnętrznym
  • Cost minimisation in unbounded multi-interface networks

    A. Kosowski, A. Navarra - 2008
    W 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...
    • Pełny tekst w serwisie zewnętrznym
  • Duże rozgłoszeniowe pola Closa

    W 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

    Artykuł 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...
    • Pełny tekst w serwisie zewnętrznym
  • Inferring perfect phylogenies with restrictions on character state transitions

    Znana 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

    Pomimo 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++....
    • Pełny tekst w serwisie zewnętrznym
  • Metaheurystyki w szeregowaniu zadań uwarunkowanych czasowo

    w artykule tym zbadano zastosowanie algorytmów metaheurystycznych w problemach szeregowania zadań uwarunkowanych czasowo. porównano wyniki algorytmu genetycznego, ewolucji różnicowej oraz symulowanego wyżarzania, z reprezentacjami rozwiązania: permutacyjną, opartą o priorytety reguł i kodowaniem przedziałowym, osiągnięte w rozwiązywaniu np-trudnego problemu 1 | pi = ai + bisi | sum wici. gdzie to możliwe, wyniki porównano z rozwiązaniami...
  • Metoda porównywania drzew filogenetycznych wykorzystująca najlżejsze doskonałe skojarzenie w grafach dwudzielnych

    Drzewa filogenetyczne przedstawiają historyczne, ewolucyjne związki pokrewieństwa między różnymi gatunkami lub różnymi osobnikami w ramach jednego gatunku. Istnieje wiele metod rekonstruowania drzew filogenetycznych. Wykorzystywanie różnych metod na tym samym zbiorze danych zazwyczaj owocuje powstaniem różnych drzew. Pojawia się zatem pytanie: jak bardzo dwa dane drzewa różnią się od siebie. W niniejszej pracy prezentujemy nową...
  • On-Line Partitioning for On-Line Scheduling with Resource Conflicts

    Within this paper, we consider the problem of on-line partitioning the sequence of jobs which are competing for non-sharable resources. As a result of partitioning we get the subsets of jobs that form separate instances of the on-line scheduling problem. The objective is to generate a partition into the minimum number of instances such that the response time of any job in each instance is bounded by a given constant. Our research...
    • Pełny tekst w serwisie zewnętrznym
  • Packing Three-Vertex Paths in 2-Connected Cubic Graphs

    A. Kosowski, P. Żyliński - ARS COMBINATORIA - 2008
    W pracy rozważano problem rozmieszczanie ścieżek P3 w 2-spójnych grafach 3-regularnych. Pokazano, że w 2-spójnym grafie 3-regularnym o n wierzchołkach można zawsze pokryć 9/11 n wierzchołków przez ścieżki P3; podano także odpowiednie oszacowania górne.
    • Pełny tekst w serwisie zewnętrznym
  • Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych

    P. Obszarski - 2008
    Problem 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.
  • program verification strategy and edge ranking of graphs

    W artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
    • Pełny tekst w serwisie zewnętrznym
  • Rearrangeable clos networks C(n,r_1,n^2-1,n,r_2) with certain restrictions for connections

    W pracy została zaproponowana nowa metoda sprawdzania przestrajalności pól Closa dla połączeń jeden do wiele. W rozważaniach zakładamy grupowanie połączeń.In the article we will propose new method of checking rearrangeability of multicast Clos networks. In the literature there is no precise method for checking rearrangeability. We focused on three-stage Clos networks without any constraints about fan-out capability. We show the...
    • Pełny tekst w serwisie zewnętrznym
  • Scanning networks with cactus topology

    Ł. Wrona - 2008
    The family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
  • Scheduling with precedence constraints: mixed graph coloring in series-parallel graphs.

    H. Furmańczyk, A. Kosowski, P. Żyliński - 2008
    W 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)$.
    • Pełny tekst w serwisie zewnętrznym
  • Some results on trading model in a consensus list coloring

    Konsensusowy 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...
  • Taking advantage of symmetries: gathering of asynchronous oblivious robots on a ring

    R. Klasing, A. Kosowski, A. Navarra - 2008
    W pracy rozważano problem rendezvous (spotkania, zebrania) dla zbioru bezpamięciowych robotów umieszczonych na wierzchołkach cyklu nieskierowanego, niewyposażonych w urządzenia komunikacyjne. Przyjęto model systemu rozproszonego występujący w literaturze pod nazwą asynchronicznego systemu z cyklami Look-Compute-Move. Problem istnienia rozwiązania rozwiązano dla wszystkich konfiguracji poczatkowych składających się z więcej niż...
    • Pełny tekst w serwisie zewnętrznym
  • The complexity of list ranking of trees

    Uporzą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...
    • Pełny tekst w serwisie zewnętrznym
  • The maximum edge-disjoint paths problem in complete graphs

    Rozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
    • Pełny tekst w serwisie zewnętrznym
  • Tighter bounds on the size of a maximum P3-matching in a cubic graph

    W pracy pokazano, że największe P3-skojarzenie dla dowolnego grafu o n>16 wierzchołkach składa się z przynajmniej 117n/152 wierzchołków.
    • Pełny tekst w serwisie zewnętrznym
  • W pełni wielomianowy schemat aproksymacyjny dla pewnego problemu szeregowania zadań uwarunkowanych czasowo

    w artykule tym rozważany jest następujący problem szeregowania zadań: dany jest jeden procesor, zbiór zadań j1, ..., jn, czas przetwarzania zadania i wynosi pi = a + bisi, zaś celem jest minimalizacja całkowitego czasu wykonywania zadań. przedstawiony został pełny wielomianowy schemat aproksymacyjny, który, o ile wszystkie współczynniki wydłużania zadań (bi) w instancji problemu są różne i większe od pewnej, ustalonej liczby u,...
  • Ważone umieszczanie grafów jako model optymalizacji komunikacji w sieciach heterogenicznych

    Umieszczenie 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...
  • 2007

  • A polynomial algorithm for some preemptive multiprocessor task scheduling problems.

    .
    • Pełny tekst w serwisie zewnętrznym
  • Algorytm budowy reprezentacji przedziałowej grafu jako heurystyka dla problemu mapowania DNA

    W pracy dokonano analizy przydatności algorytmu Corneil'a budowy reprezentacji przedziałowej grafu jako heurystyki dla problemu tworzenia map fizycznych DNA. Prezentowana analiza dotyczy dwóch osobno rozpatrywanych przypadków, w których do danych wzorcowych wprowadzamy odpowiednio błędy negatywne (reprezentujące niedobór informacji) oraz błędy pozytywne (reprezentujące fałszywe informacje). Rozpatrywany algorytm zachowuje się znacznie...
  • Application of an online judge & contester system in academic tuition

    Praca 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.
  • Cooperative mobile guards in grids

    Praca dotyczy problemu strzeżenia dwuwymiarowych krat ortogonalnych, przy założeniu, że obszar widoczności strażnika obejmuje jedną ulicę oraz wszystkie ulice ją przecinające. Rozważano wariant straży słabo współpracujących, w którym dodatkowo każdy strażnik musi widzieć przynajmniej jednego innego strażnika. Podano dowód NP-trudności problemu optymalizacyjnego w przypadku ogólnym, algorytm dokładny o złożoności O(n log n) dla...
    • Pełny tekst w serwisie zewnętrznym
  • Cost minimisation in multi-interface networks

    R. Klasing, A. Kosowski, A. Navarra - 2007
    Praca dotyczy problemu minimalizacji energii poprzez selektywne odłączanie urządzeń komunikacyjnych w wielointerfejsowych sieciach bezprzewodowych w taki sposób, by zapewnić realizację wymaganego grafu połączeń. Sformułowano problem optymalizacyjny, podano wyniki dotyczące jego trudności i zaproponowano algorytmy optymalizacyjne.
    • Pełny tekst w serwisie zewnętrznym
  • Easy and hard instances of arc ranking in directed graphs

    Artykuł 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...
  • Efficient list cost coloring of vertices and/or edges of some sparse graphs

    Rozważ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.