Search
Department of Algorithms and Systems Modelling
Publications
Filters
total: 517
Catalog Publications
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublicationWe consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard,...
-
Równowaga strategiczna dla zbiorów defensywnych w drzewach
PublicationW 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...
-
Gdańska Międzynarodowa Szkoła Letnia na WETI
PublicationW dniach 5-12 września 2017 roku Katedra Algorytmów i Modelowania Systemów23, przy wydatnej pomocy,WETI, zorganizowała Międzynarodową Szkołę Letnią poświęconą algorytmom dla problemów optymalizacji dyskretnej.
-
Dynamic F-free Coloring of Graphs
PublicationA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
On-line Search in Two-Dimensional Environment
PublicationWe consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. As a way of modeling two-dimensional shapes, we restrict our attention to networks that are embedded into partial grids:...
-
ANALIZA MOŻLIWOŚCI WYKORZYSTANIA TRANSFORMACJI FALKOWEJ DO DETEKCJI NIEZAJĘTYCH PASM CZĘSTOTLIWOŚCI
PublicationCelem pracy była implementacja oraz wykonanie badań efektywności wybranej metody wykrywania niezajętych zasobów częstotliwości, opartej na wyznaczaniu entropii sygnału z wykorzystaniem analizy falkowej. W referacie przedstawiono podstawy teoretyczne rozważanych zagadnień, wyniki przeprowadzonych badań laboratoryjnych i ich analizę oraz wnioski.
-
Brief Announcement: Energy Constrained Depth First Search
PublicationDepth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due...
-
Metody oceny jakości łączy bezprzewodowych wykorzystywanych w systemie netBaltic
PublicationPrzedstawiono metodę oceny jakości łączy, opracowaną w ramach projektu netBaltic, która powstała w wyniku analizy danych zgromadzonych podczas wielu kampanii pomiarowych na wodach Morza Bałtyckiego oraz badań i testów prowadzonych w środowisku laboratoryjnym. Przedstawiono definicję parametru LQI (Link Quality Indicator) oraz sposób jego wyznaczania dla sieci komórkowych 3G i LTE oraz dla łączy bezprzewodowych WiFi. Zaprezentowano...
-
Oxygen sensitivity of hydrogenesis’ and methanogenesis’
PublicationIn the chapter, results of dark fermentation of sour cabbage in presence of oxygen with concentrations 2-9% are presented. The presence of oxygen in such concentration inhibits methanogesis (and methane production more than 2 times) and increases hydrogen production 6 times. It also shortens the fermentation process above 40%.
-
Restricted open shop scheduling
PublicationIn the real applications the open shop scheduling models often require some additional constraints and adequate models. We concern the restrictions in the open shop scheduling related to an instance of the problem and to a feasible solution. Precisely, we require that each jobs consists of the bounded number of operations and each machine has a bounded load (i.e., the total number of operations executed on this machine in a schedule)....
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublicationW 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ć...
-
The Snow Team Problem
PublicationWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset~$\cS$ of vertices of a digraph $D$ and a positive integer $k$, the objective is to determine whether there is a subgraph $H=(\cV_H,\cA_H)$ of $D$ such that (a) $\cS \subseteq \cV_H$, (b)...
-
Realizacja zadań w grafie przez grupę mobilnych jednostek
PublicationGrupa mobilnych jednostek, nazywanych także agentami, jest umiejscowiona w jednym lub wielu wierzchołkach grafu nazywanych bazami. Stamtąd poruszając się po z góry znanym (offline) lub nieznanym (online) grafie muszą wykonać powierzone im zadanie, takie jak przeszukanie grafu, spotkanie, dekontaminacja grafu czy wybór lidera. Celem jest znalezienie optymalnej, rozproszonej, deterministycznej strategii (sekwencji ruchów jednostek),...
-
No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs
PublicationIn the open shop scheduling with bioperational jobs each job consists of two unit operations with a delay between the end of the first operation and the beginning of the second one. No-wait requirement enforces that the delay between operations is equal to 0. No-idle means that there is no idle time on any machine. We model this problem by the interval incidentor (1, 1)-coloring (IIR(1, 1)-coloring) of a graph with the minimum...
-
Szybkość przeszukiwania grafu
PublicationPrzeszukiwanie grafu pojawiło się jako problem matematyczny ponad 40 lat temu i w najogólniejszej wersji zajmuje się odszukiwaniem jednostki-uciekiniera niezależnie od jego poczynań. Od tamtej pory uzyskano wiele wyników odpowiadających na pytanie o minimalną ilość poszukujących jednostek w różnorodnych modelach, czyli odpowiednią liczbę przeszukiwawczą (ang. serach number) grafu. Popularne warianty problemów przeszukiwania obejmują...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublicationA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
Non-monotone graph searching models
PublicationGraph searching encompasses a variety of different models, many of which share a property that in optimal strategies fugitive can never access once searched regions. Monotonicity, as it is called, is vital in many established results in the field however its absence significantly impedes the analysis of a given problem. This survey attempts to gather non-monotone models, that are less researched in effort of summarizing the results...
-
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...
-
Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów
PublicationRozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy...
-
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
PublicationA graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
-
Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs
PublicationIn this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring.
-
Independence in uniform linear triangle-free hypergraphs
PublicationThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
Elementy kwantowego modelu obliczeń i algorytmiki kwantowej : łagodne wprowadzenie do informatyki kwantowej
PublicationJuż dziś wiadomo, że z chwilą udanej realizacji komputera kwantowego maszyna ta będzie pozwalała na znajdowanie rozwiązań problemów obliczeniowych leżących poza zasięgiem komputerów klasycznych. Opracowano szereg algorytmów kwantowych, z których największą sławą cieszy się procedura Shora, pozwalająca efektywnie dokonywać tzw. faktoryzacji, tj. rozkładu bardzo dużych liczb naturalnych na czynniki pierwsze. Na trudności obliczeniowej...
-
Evolving gene regulatory networks controlling foraging strategies of prey and predators in an artificial ecosystem
PublicationCo-evolution of predators and prey is an example of an evolutionary arms race, leading in nature to selective pressures in positive feedback. We introduce here an artificial life ecosystem in which such positive feedback can emerge. This ecosystem consists of a 2-dimensional liquid environment and animats controlled by evolving artificial gene regulatory networks encoded in linear genomes. The genes in the genome encode chemical...
-
Evolution of chemotaxis in single-cell artificial organisms
PublicationThe model of a liquid two-dimensional environment, which is based on physics of diffusion, allows us to simulate the diffusion of morphogenes. Artificial organisms move using a chemotaxis reacting to concentration difference. Organisms are controlled by a gene regulatory network coded in a linear genome and reproduce by division. We made a lot of experiments presenting organisms’ behaviour in various environment conditions. We...
-
Evolution of artificial single-cell organisms foraging for resources in a 3-dimensional environment
PublicationForaging for resources is a simple cognitive task that even one-celled biological organisms can ac- complish. We present an Artificial Life system in which artificial unicellular organisms (animats) forage for food in a 3-dimensional simulated liquid environment. The movement of animats is controlled by evolving artificial gene regulatory networks encoded in linear genomes. When an animat consumes enough food, it produces offspring...
-
Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains
PublicationWe consider two versions of the rendezvous problem: exact RV, when the points representing agents have to coincide at some time, and e-RV, when these points have to get at distance less than e in the terrain. In any terrain, each agent chooses its trajectory, but the movements of the agent on this trajectory are controlled by an adversary that may, e.g. speed up or slow down the agent.
-
How to meet when you forget: log-space rendezvous in arbitrary graphs
PublicationProblem rendezvous został dogłębnie zbadany, zarówno dla agendów anonimowych jak i poetykietowanych. zbadano też problem eksploracji grafu za pomocą agentów mobilnych.
-
Łagodne wprowadzenie do analizy algorytmów
PublicationKsiążka jest 11. wydaniem podręcznika akademickiego poświęconego podstawom algorytmiki. Składa się z trzech rozdziałów. Rozdział 1 daje podstawy formalne niezbędne przy analizie algorytmów pod kątem złożoności obliczeniowej. Rozdział 2 wprowadza w zagadnienia analizy algorytmów z różnych punktów widzenia.Rozdział 3 przedstawia podstawowe struktury danych.
-
Minimal double dominating sets in trees
PublicationWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
An algorithm for listing all minimal double dominating sets of a tree
PublicationWe provide an algorithm for listing all minimal double dominating sets of a tree of order $n$ in time $\mathcal{O}(1.3248^n)$. This implies that every tree has at most $1.3248^n$ minimal double dominating sets. We also show that this bound is tight.
-
Bounds on the vertex-edge domination number of a tree
PublicationA vertex-edge dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every edge of $G$ is incident with a vertex of $D$ or a vertex adjacent to a vertex of $D$. The vertex-edge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertex-edge dominating set of $G$. We prove that for every tree $T$ of order $n \ge 3$ with $l$ leaves and $s$ support vertices we have $(n-l-s+3)/4...
-
Zgred - Zgred Graph Editor
PublicationThe paper presents a graph editor that was developed as a supplementary tool for the Koala graph library. We discuss its requirements, design choices and main ideas behind the implementation. The later part of the paper is meant to be a brief user manual, as we go through the functionality provided by the editor
-
The Backbone Coloring Problem for Bipartite Backbones
PublicationLet G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks
PublicationIn 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects....
-
On trees attaining an upper bound on the total domination number
PublicationA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 69-75] established the following upper bound on the total domination...
-
On the hardness of computing span of subcubic graphs
PublicationIn the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used.
-
Applications of semi-definite optimization in quantum information protocols
PublicationThis work is concerned with the issue of applications of the semi-definite programming (SDP) in the field of quantum information sci- ence. Our results of the analysis of certain quantum information protocols using this optimization technique are presented, and an implementation of a relevant numerical tool is introduced. The key method used is NPA discovered by Navascues et al. [Phys. Rev. Lett. 98, 010401 (2007)]. In chapter...
-
Zastosowanie komputerów w dziedzinie wyszukiwania strategii optymalnych w grach logicznych
PublicationProblem jaki stanowi wyszukiwanie strategii optymalnej w grach logicznych jest bardzo złożony. Można go podzielić na następujące podproblemy: obliczeniowy, pamięciowy oraz operacji wejścia/wyjścia. Jednak rosnąca z roku na rok siła obliczeniowa komputerów, ilość pamięci oraz prędkość transferu danych pomiędzy podzespołami zarówno lokalnymi jak i rozproszonymi, a także wzrost skuteczności wykorzystywanych technik algorytmicznych...
-
Gdańska Międzynarodowa Szkoła Letnia na WETI
PublicationW dniach 6-12 lipca 2019 roku Katedra Algorytmów i Modelowania Systemów zorganizowała 3. Międzynarodową Szkołę Letnią poświęconą algorytmom dla problemów optymalizacji dyskretnej.
-
Czy komputer może zrobić błąd rachunkowy?
PublicationW szkole błędy rachunkowe nie są mile widziane, w dodatku zazwyczaj nie wolno na lekcjach matematyki używać kalkulatorów. Jaka szkoda! Przecież kalkulator nigdy się nie myli! Ale czy na pewno?
-
Zagadkowe obrazki binarne
PublicationCzy wiesz, że za pomocą liczb można kodować obrazki? Dziś odkodujemy i narysujemy takie obrazki, a przy okazji poćwiczymy zamianę liczb z systemu dziesiętnego na dwójkowy, czyli binarny.
-
Multi-agent graph searching and exploration algorithms
PublicationA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
-
Kształcenie nauczycieli informatyki w zakresie opracowywania komputerowych multimedialnych środków dydaktycznych.
PublicationW artykule przedstawiono studia podyplomowe ''Internet i multimedia'', których słuchaczami są nauczyciele informatyki szkół średnich i gimnazjów. Opisano program kształcenia tych studiów, wyróżniając w nim dwa zasadnicze nurty:zapoznanie słuchaczy ze współczesnymi trendami rozwoju technologii informacyjnej oraz nauczenie słuchaczy opracowywania komputerowych pomocy dydaktycznych wykorzystujących zasoby multimedialne...
-
Prezentacje multimedialne z wykorzystaniem środowiska Flash
PublicationW referacie przedstawiono istotne cechy środowiska programowego pakietu Macromedia-Flash umożliwiającego tworzenie multimedialnych aplikacji edukacyjnych.
-
Komputerowy system sieciowy wspomagający ocenianie uczniów
PublicationW referacie przedstawiono funkcje użytkowe sieciowego systemu komputerowego umożliwiające utworzenie przez nauczycieli testów wyboru z dowolnej dziedziny, przeprowadzenie lekcji polegającej na rozwiązywaniu testów, automatyczne ocenianie rozwiązań, sporządzanie statystyk oraz powiadamianie uczniów o wynikach testów.
-
Sieciowy system komputerowy wspomagający testowanie wiedzy uczniów
PublicationW referacie przedstawiono organizację sieciowego systemu komputerowego wspomagającego tworzenie i przeprowadzanie testów. Omówiono przypadki użycia systemu z punktu widzenia administratora sieci, nauczyciela i ucznia, a także przypadki wspólne dla wszystkich użytkowników systemu. Podano opis interfejsu dla poszczególnych grup użytkowników.
-
Kształcenie w firmie symulacyjnej
PublicationW artykule opisano zadania i funkcje firmy symulacyjnej jako nowego modelu kształcenia zawodowego. Przebieg edukacji w firmie symulacyjnej przedstawiono na przykładzie Przedsiębiorstwa Symulacyjnego CKU-Modex w Sopocie. W zakończeniu artykułu opisano i uzasadniono zalety takiego sposobu kształcenia.
-
III Konkurs Informatyczno-Techniczny
PublicationW artykule przedstawiono cele oraz przebieg III Konkursu Informatyczno-Technicznego "InfoTech" dla młodzieży szkół średnich. Zaprezentowano przykładowe pytania i zadania ilustrujące tematykę, zakres wiedzy i poziom konkursu. Autorzy kończą artykuł uwagami i sugestiami skierowanymi do organizatorów następnej edycji konkursu.