# Katedra Algorytmów i Modelowania Systemów

## Publikacje

• wyników na stronę:
• rok:
tytuł:

wszystkich: 396

## Katalog

• ### 2014

• #### Evolution of Animats Following a Moving Target in an Artificial Ecosystem

Many biological animals, even microscopically small, are able to track moving sources of food. In this paper, we investigate the emergence of such behavior in artificial animals (animats) in a 2-dimensional simulated liquid environment. These "predators" are controlled by evolving artificial gene regulatory networks encoded in linear genomes. The fate of the predators is determined only by their ability to gather food and reproduce—no...
• Pełny tekst w serwisie zewnętrznym
• #### Interval incidence coloring of bipartite graphs

In this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
• Pełny tekst w serwisie zewnętrznym
• #### Leader election for anonymous asynchronous agents in arbitrary networks

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...
• Pełny tekst w serwisie zewnętrznym
• #### Łagodne wprowadzenie do analizy algorytmów

M. Kubale - 2014
Książ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

We 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.
• #### On practical application of Shannon theory to character recognition and more

M. Jurkiewicz - 2014
Let us consider an optical character recognition system, which in particular can be used for identifying objects that were assigned strings of some length. The system is not perfect, for example, it sometimes recognizes wrongly the characters "Y" and "V". What is the largest set of strings of given length for the system under consideration, which can be mutually correctly recognized, and the corresponding objects correctly identified?...
• #### Properties of dimension witnesses and their semidefinite programming relaxations

P. Mironowicz, H. Li, M. Pawłowski - PHYSICAL REVIEW A - 2014
In this paper we develop a method for investigating semi-device-independent randomness expansion protocols that was introduced in Li et al. [H.-W. Li, P. Mironowicz, M. Pawłowski, Z.-Q. Yin, Y.-C. Wu, S. Wang, W. Chen, H.-G. Hu, G.-C. Guo, and Z.-F. Han, Phys. Rev. A 87, 020302(R) (2013)]. This method allows us to lower bound, with semi-definite programming, the randomness obtained from random number generators based on dimension...
• Pełny tekst w serwisie zewnętrznym
• #### Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs

S. Das, D. Dereniowski, A. Kosowski, P. Uznański - 2014
We study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...
• Pełny tekst w serwisie zewnętrznym
• #### Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks

D. Dereniowski, Ł. Kuszner, A. Kosowski, R. Klasing - 2014
We introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...
• Pełny tekst w serwisie zewnętrznym
• #### Sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych

H. Furmańczyk, M. Kubale - 2014
W pracy rozpatrywane są sprawiedliwe i półsprawiedliwe pokolorowania grafów kubicznych. Pokazano, że w odróżnieniu od tego pierwszego, który jest łatwy, problem istnienia pokolorowań półsprawiedliwych jest NP-zupełny w szerokim zakresie parametrów grafów.
• #### The Backbone Coloring Problem for Small Graphs

In this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...
• Pełny tekst w serwisie zewnętrznym
• #### The Complexity of Zero-Visibility Cops and Robber

D. Dereniowski, D. Dyer, R. Tifenbach, B. Yang - 2014
In this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
• Pełny tekst w serwisie zewnętrznym
• #### Time versus space trade-offs for randezvous in trees

J. Czyzowicz, A. Kosowski, A. Pelc - DISTRIBUTED COMPUTING - 2014
Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory...
• Pełny tekst w serwisie zewnętrznym
• #### Zgred - Zgred Graph Editor

The 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
• ### 2013

• #### 2-bondage in graphs

A 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The 2-bondage number of G, denoted by b_2(G), is the minimum cardinality among all sets of edges E' subseteq E such that gamma_2(G-E') > gamma_2(G). If for every E' subseteq E we have...
• Pełny tekst w serwisie zewnętrznym
• #### An Algorithm for Listing All Minimal 2-Dominating Sets of a Tree

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3248n) . This implies that every tree has at most 1.3248 n minimal 2-dominating sets. We also show that this bound is tigh.
• Pełny tekst w serwisie zewnętrznym
• #### Certain family of analytical solutions of nonlinear von Neumann equations

P. Mironowicz - 2013
In this paper we present a slight generalization of certain type of Darboux transformation, that may be used sub-sequently in a convenient way. This method allows to obtain families of solutions of nonlinear von Neumann equations, that are used in particular in DNA modeling.
• Pełny tekst w serwisie zewnętrznym
• #### Deterministic rendezvous of asynchronous bounded-memory agents in polygonal terrains

J. Czyzowicz, A. Kosowski, A. Pelc - THEORY OF COMPUTING SYSTEMS - 2013
We 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.
• Pełny tekst w serwisie zewnętrznym
• #### Drugie Igrzyska Akademii ETI

W sobotę 2 lutego 2013 r. odbyły się drugie Igrzyska Akademii ETI zorganizowane przez Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej dla uczniów szkół ponadgimnazjalnych regionu. Celem Igrzysk było zwiększenie zainteresowania informatyką młodzieży szkół ponadgimanzjalnych i promocja studiów na Wydziale ETI PG. W tegorocznych Igrzyskach udział wzięli uczniowie z 7 szkół województwa pomorskiego.
• Pełny tekst w serwisie zewnętrznym
• #### Elementy kwantowego modelu obliczeń i algorytmiki kwantowej : łagodne wprowadzenie do informatyki kwantowej

K. Giaro - 2013
Już 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...
• Pełny tekst w serwisie zewnętrznym
• #### Equitable coloring of corona products of graphs

H. Furmańczyk, K. Kaliraj, M. Kubale, J. Vernold Vivin - Advances and Applications in Discrete Mathematics - 2013
In this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
• Pełny tekst w serwisie zewnętrznym
• #### Evolution of artificial single-cell organisms foraging for resources in a 3-dimensional environment

Foraging for resources is a simple cognitive task that even one-celled biological organisms can ac- complish. We present an Artiﬁcial Life system in which artiﬁcial unicellular organisms (animats) forage for food in a 3-dimensional simulated liquid environment. The movement of animats is controlled by evolving artiﬁcial gene regulatory networks encoded in linear genomes. When an animat consumes enough food, it produces offspring...
• #### Evolving gene regulatory networks controlling foraging strategies of prey and predators in an artificial ecosystem

Co-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 artiﬁcial life ecosystem in which such positive feedback can emerge. This ecosystem consists of a 2-dimensional liquid environment and animats controlled by evolving artiﬁcial gene regulatory networks encoded in linear genomes. The genes in the genome encode chemical...
• #### Fast Collaborative Graph Exploration

D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk, P. Uznański - LECTURE NOTES IN COMPUTER SCIENCE - 2013
We study the following scenario of online graph exploration. A team of k agents is initially located at a distinguished vertex r of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure...
• Pełny tekst w serwisie zewnętrznym
• #### Minimal 2-dominating sets in Trees

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time O(1.3247^n). This leads to that every tree has at most 1.3247^n minimal 2-dominating sets. We also show that thisbound is tight.
• Pełny tekst w serwisie zewnętrznym
• #### Non-isolating 2-bondage in graphs

A 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....
• Pełny tekst w serwisie zewnętrznym
• #### On a matching distance between rooted phylogenetic trees

The Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...
• Pełny tekst w serwisie zewnętrznym
• #### On minimum cost edge searching

We consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
• Pełny tekst w serwisie zewnętrznym
• #### On the ratio between 2-domination and total outer-independent domination numbers of trees

A 2-dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)D has a at least two neighbors in D. A total outer-independent 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, and the set V(G)D is independent. The 2-domination (total outer-independent domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (total...
• Pełny tekst w serwisie zewnętrznym
• #### On trees with double domination number equal to 2-domination number plus one

A vertex of a graph is said to dominate itself and all of its neighbors. A subset D subseteq V(G) is a 2-dominating set of G if every vertex of V(G)D is dominated by at least two vertices of D, while it is a double dominating set of G if every vertex of G is dominated by at least two vertices of D. The 2-domination (double domination, respectively) number of a graph G is the minimum cardinality of a 2-dominating (double dominating,...
• Pełny tekst w serwisie zewnętrznym
• #### On-line ranking of split graphs

A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...
• Pełny tekst w serwisie zewnętrznym
• #### Optimal edge-coloring with edge rate constraints

D. Dereniowski, W. Kubiak, B. Ries, Y. Zwols - NETWORKS - 2013
We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable....
• Pełny tekst w serwisie zewnętrznym
• #### Partial dominated schedules and minimizing the total completion time of deteriorating jobs

A problem of scheduling deteriorating jobs on a single processor is considered. The processing time of a job is given by a function pi=ai+bisi, where si is the starting time of the job, ai>=0, bi>=0, for i=1,...,n. Jobs are non-preemptive and independent and there are neither ready times nor deadlines. The goal is to minimize the total weighted completion time. We show how to employ the concept of non-dominated schedules to construct...
• Pełny tekst w serwisie zewnętrznym
• #### Robustness of quantum-randomness expansion protocols in the presence of noise

P. Mironowicz, M. Pawłowski - PHYSICAL REVIEW A - 2013
In this paper we investigate properties of several randomness generation protocols in the device independent framework. Using Bell-type inequalities it is possible to certify that the numbers generated by an untrusted device are indeed random. We present a selection of certificates which guarantee two bits of randomness for each run of the experiment in the noiseless case and require the parties to share a maximally entangled state....
• Pełny tekst w serwisie zewnętrznym
• #### Three-fast-searchable graphs

D. Dereniowski, O. Yasar Diner, D. Dyer - DISCRETE APPLIED MATHEMATICS - 2013
In the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
• Pełny tekst w serwisie zewnętrznym
• #### Trees having many minimal dominating sets

We provide an algorithm for listing all minimal dominating sets of a tree of order n in time O(1.4656^n). This leads to that every tree has at most 1.4656^n minimal dominating sets. We also give an infinite family of trees of odd and even order for which the number of minimal dominating sets exceeds 1.4167^n, thus exceeding 2^{n/2}. This establishes a lower bound on the running time of an algorithm for listing all minimal dominating...
• Pełny tekst w serwisie zewnętrznym
• #### Zero-Visibility Cops and Robber Game on a Graph

D. Dereniowski, D. Dyer, R. Tifenbach, B. Yang - LECTURE NOTES IN COMPUTER SCIENCE - 2013
We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops & robber game in one way: the robber is invisible. We show that this model is not monotonic. We also provide bounds on both the zero-visibility copnumber and monotonic zero-visibility copnumber in terms of the pathwidth.
• Pełny tekst w serwisie zewnętrznym
• ### 2012

• #### A construction for the hat problem on a directed graph

A team of n players plays the following game. After a strategy session, each player is randomly fitted with a blue or red hat. Then, without further communication, everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. Visibility is defined by a directed graph; that is, vertices correspond to players, and a player can see each player to whom he is connected by an arc. The...
• Pełny tekst w serwisie zewnętrznym
• #### A lower bound on the double outer-independent domination number of a tree

A vertex of a graph is said to dominate itself and all of its neighbors. A double outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D, and the set V(G)D is independent. The double outer-independent domination number of a graph G, denoted by gamma_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We...
• Pełny tekst w serwisie zewnętrznym
• #### A Point Set Connection Problem for Autonomous Mobile Robots in a Grid

A. Kosowski, I. Suzuki, P. Zylinski - COMPUTING AND INFORMATICS - 2012
Consider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given...
• Pełny tekst w serwisie zewnętrznym
• #### An efficient algorithm for finding ideal schedules

E. Coffman Jr., D. Dereniowski, W. Kubiak - ACTA INFORMATICA - 2012
Podejmujemy problem szeregowania zadań jednostkowych z zadanymi czasamy przybycia i zależnościami kolejnościowymi. Uszeregowanie jest idealne jeśli jednocześnie minimalizuje maksymalny oraz średni czas zakończenia zadania. Podajemy przyklad pokazujący, że uszeregowania idealne nie istnieją dla relacji zależności zadań będącej drzewem, gdy dopuścimy możliwość wystąpienia przerwań. Z drugiej strony podajemy algorytm o złożoności...
• Pełny tekst w serwisie zewnętrznym
• #### An upper bound on the total outer-independent domination number of a tree

A total outer-independent dominating set of a graph G=(V(G),E(G)) is a set D of vertices of G such that every vertex of G has a neighbor in D, and the set V(G)D is independent. The total outer-independent domination number of a graph G, denoted by gamma_t^{oi}(G), is the minimum cardinality of a total outer-independent dominating set of G. We prove that for every tree T of order n >= 4, with l leaves and s support vertices we have...
• Pełny tekst w serwisie zewnętrznym
• #### Approximate search strategies for weighted trees

W pracy podajemy 3-przybliżony algorytm dla problemu spójnego przeszukiwania drzew ważonych.
• Pełny tekst w serwisie zewnętrznym
• #### Colorings of the Strong Product of Circulant Graphs

M. Jurkiewicz - 2012
Graph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.
• #### Drawing maps with advice

Rozważ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ę...
• Pełny tekst w serwisie zewnętrznym
• #### Dynamic coloring of graphs

P. Borowiecki, E. Sidorowicz - FUNDAMENTA INFORMATICAE - 2012
Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN's, channel assignment in WDM optical networks as well as traffic scheduling. In...
• #### Evolution of chemotaxis in single-cell artificial organisms

The 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...
• #### From Pathwidth to Connected Pathwidth

W pracy przedstawiono dowód faktu, że spójna szerokość ścieżkowa grafu wynosi co najwyżek 2k+1, gdzie k jest jego szerokością ścieżkową. Dowód jest konstruktywny, tzn., został skonstruowany algorytm, który dla podanej na wejściu dekompozycji grafu o szerekości k zwraca dekompozycję spóją o szerekości co najwyżej 2k+1.
• Pełny tekst w serwisie zewnętrznym
• #### Graph Decomposition for Memoryless Periodic Exploration

A. Kosowski, A. Navarra - ALGORITHMICA - 2012
We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels within the range 1 to deg (v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex...
• Pełny tekst w serwisie zewnętrznym
• #### Greedy algorithms for backbone graph coloring in KOALA library

K. Turowski - 2012