Department of Algorithms and Systems Modelling - Administrative Units - Bridge of Knowledge

Search

Department of Algorithms and Systems Modelling

Filters

total: 524

  • Category
  • Year
  • Options

clear Chosen catalog filters disabled

Catalog Publications

Year 2013
  • Equitable coloring of corona products of graphs
    Publication
    • H. Furmańczyk
    • K. Kaliraj
    • M. Kubale
    • J. Vernold Vivin

    - Advances and Applications in Discrete Mathematics - Year 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.

    Full text available to download

  • Evolution of artificial single-cell organisms foraging for resources in a 3-dimensional environment
    Publication

    Foraging 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...

  • Evolving gene regulatory networks controlling foraging strategies of prey and predators in an artificial ecosystem
    Publication

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

  • Fast Collaborative Graph Exploration
    Publication

    - LECTURE NOTES IN COMPUTER SCIENCE - Year 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...

    Full text to download in external service

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

    Full text to download in external service

  • 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)....

    Full text available to download

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

    Full text available to download

  • On minimum cost edge searching
    Publication

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

    Full text available to download

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

    Full text to download in external service

  • 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,...

    Full text to download in external service

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

    Full text available to download

  • Optimal edge-coloring with edge rate constraints
    Publication

    - NETWORKS - Year 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....

    Full text to download in external service

  • Partial dominated schedules and minimizing the total completion time of deteriorating jobs
    Publication

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

    Full text to download in external service

  • Robustness of quantum-randomness expansion protocols in the presence of noise
    Publication

    - PHYSICAL REVIEW A - Year 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....

    Full text available to download

  • Three-fast-searchable graphs
    Publication

    - DISCRETE APPLIED MATHEMATICS - Year 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...

    Full text available to download

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

    Full text to download in external service

  • Zero-Visibility Cops and Robber Game on a Graph
    Publication

    - LECTURE NOTES IN COMPUTER SCIENCE - Year 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.

    Full text to download in external service

Year 2012
  • A construction for the hat problem on a directed graph
    Publication

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

    Full text available to download

  • A lower bound on the double outer-independent domination number of a tree
    Publication

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

    Full text available to download

  • A Point Set Connection Problem for Autonomous Mobile Robots in a Grid
    Publication

    - COMPUTING AND INFORMATICS - Year 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...

    Full text to download in external service

  • An efficient algorithm for finding ideal schedules
    Publication

    - ACTA INFORMATICA - Year 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...

    Full text to download in external service

  • An upper bound on the total outer-independent domination number of a tree
    Publication

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

    Full text available to download

  • Approximate search strategies for weighted trees
    Publication

    W pracy podajemy 3-przybliżony algorytm dla problemu spójnego przeszukiwania drzew ważonych.

    Full text available to download

  • Colorings of the Strong Product of Circulant Graphs
    Publication
    • M. Jurkiewicz

    - Year 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.

  • Double bondage in graphs
    Publication

    A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets...

    Full text to download in external service

  • 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ę...

    Full text to download in external service

  • Dynamic coloring of graphs
    Publication

    - FUNDAMENTA INFORMATICAE - Year 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
    Publication

    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.

    Full text to download in external service

  • Graph Decomposition for Memoryless Periodic Exploration
    Publication

    - ALGORITHMICA - Year 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...

    Full text to download in external service

  • Greedy algorithms for backbone graph coloring in KOALA library
    Publication

    - Year 2012

  • How to meet when you forget: log-space rendezvous in arbitrary graphs
    Publication

    - DISTRIBUTED COMPUTING - Year 2012

    Problem rendezvous został dogłębnie zbadany, zarówno dla agendów anonimowych jak i poetykietowanych. zbadano też problem eksploracji grafu za pomocą agentów mobilnych.

    Full text to download in external service

  • Igrzyska Akademii ETI : Konkurs dla młodych talentów informatycznych, potencjalnych studentów WETI
    Publication

    Sprawozdanie z pierwszych Igrzysk Akademii ETI, które odbyły się 21 stycznia 2012 r.

    Full text to download in external service

  • Katedra Algorytmów i Modelowania Systemów

    Przedstawiono podstawowe informacje nt. Katedry Algorytmów i Modelowania Systemów Wydziału Elektroniki, Telekomunikacji i Informatyki PG. W szczególności przedstawiono rys historyczny, działalność dydaktyczną, badania podstawowe, nagrody i wyróżnienia oraz ofertę dla przemysłu.

  • Kodowanie niedostarczonej do odbiorców informacji w systemach satelitarnych z wolnym kanałem zwrotnym
    Publication
    • M. Jurkiewicz

    - Year 2012

    W poniższym artykule przedstawiono problem kodowania źródła satelitarnego opisany przez Birka i Kola. Przytoczono również nieoptymalne kodowanie dla postawionego problemu oraz miarę określającą możliwości takiego kodowania oraz kilka przykładów, w których wcześniej wspomniane kodowanie staje się optymalne.

  • Kolorowanie grafów z ograniczeniami na liczbę wierzchołków w określonym kolorze = Graph coloring model with restrictions on cardinalities of vertexes in particular color
    Publication

    - Year 2012

    W artykule rozważamy problem takiego kolorowania grafów, w którym klasy kolorów mają ograniczoną z góry moc. Zagadnie to znajduje ciekawe zastosowania praktyczne i jest naturalnym uogólnieniem problemu kolorowania grafów. W artykule ustalamy złożoność obliczeniową dla grafów pełnych $r$-dzielnych i dla kilku innych prostych klas grafów oraz dla problemu dwukolorowania.

  • METODA WYZNACZANIA ZŁOŻONOŚCI PODPRZESTRZENI STANÓW PLANSZOWYCH GIER LOGICZNYCH LOGICZNYCH

    Jedna z metod rozwiązywania gier jest analiza wsteczna. Jej skuteczność jest ograniczona wielkością przestrzeni stanów gry, która stanowi rozwiązywany problem. Pierwszego takiego oszacowania dokonał Claude E. Shannon odnośnie gry szachy w połowie minionego stulecia. Ważnym elementem jest podział takiej przestrzeni na mniejsze części, które mogą być rozwiązywane niezależnie lub z wykorzystaniem stosunkowo niewielkiej ilości informacji z...

    Full text to download in external service

  • Metody optymalizacji dyskretnej w analizie podobieństwa drzew filognetycznych
    Publication

    - Year 2012

  • Minimalizacja szerokości pasma w sieciach radiowych metodami szkieletowego kolorowania grafów
    Publication

    Artykuł poświęcony jest szkieletowemu kolorowaniu grafów, które jest matematycznym modelem dla problemu minimalizacji szerokości pasma w sieciach radiowych. Badamy w nim zależność szkieletowej liczby chromatycznej od parametrów zagadnienia. Dowodzimy, że dla dużych wartości parametrów ta zależność jest liniowa.

  • Modele i metody kolorowania grafów. Część II
    Publication

    Niniejszy artykuł jest drugą częścią 2-odcinkowego cyklu przeglądowego na temat modeli i metod kolorowania grafów. Przedstawiono w nim najważniejsze, z punktu widzenia zastosowań, modele kolorowania grafów. W szczególności pokazano różne kryteria i ograniczenia modyfikujące kolorowanie klasyczne. Ponieważ kolorowanie we wszystkich tych odmianach i wariantach jest NP-trudne, podano oszacowania na liczbę chromatyczną (indeks chromatyczny)...

    Full text to download in external service

  • On Optimal Backbone Coloring of Split and Threshold Graphs with Pairwise Disjoint Stars
    Publication

    - Year 2012

  • On the hat problem on a graph
    Publication

    The topic of this paper is the hat problem in which each of n players is uniformly and independently fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning....

    Full text available to download

  • On the size of identifying codes in triangle-free graphs
    Publication

    - DISCRETE APPLIED MATHEMATICS - Year 2012

    In an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...

    Full text available to download

  • On trees with double domination number equal to 2-outer-independent domination number plus one

    A vertex of a graph is said to dominate itself and all of its neighbors. A double 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. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G=(V,E), a subset D subseteq V(G) is a 2-dominating set if every vertex of V(G)D has at least two neighbors...

    Full text to download in external service

  • Product Graph Invariants with Applications in the Theory of Information
    Publication

    - Year 2012

    There are a large number of graph invariants. In the paper, we consider some of them, e.g. the independence and chromatic numbers. It is well know that we cannot efficiently calculate these numbers for arbitrary graphs. In the paper we present relations between these invariants and concepts from the theory of information. Concepts such as source coding and transmission over a noisy channel with zero probability of error are modeled...

  • Properties of the triset metric for phylogenetic trees
    Publication

    - Year 2012

    the following paper presents a new polynomial time metric for unrootedphylogenetic trees (based on weighted bipartite graphs and the method ofdetermining a minimum perfect matching) and its properties. also many its properties are presented.

    Full text to download in external service

  • Routing equal-size messages on a slotted ring
    Publication

    - JOURNAL OF SCHEDULING - Year 2012

    Analizujemy problem routingu wiadomości w sieci slotted ring, biorąc pod uwagę dwa kryteria optymalizacyjne: długość uszeregowania oraz liczbę 'cykli' pracy sieci. Optymalny routing dla wiadomości o rozmiarze k jest silnie NP-trudny, natomiast dla k=q, gdzie q jest rozmiarem sieci, można obliczyć w czsie O(n^2log n) dla pierwszego kryterium. Podajemy również algorytm o czasie działania O(nlog n) oraz o stałym współczynniku dobroci....

    Full text to download in external service

  • Some Exact Values of Shannon Capacity for Evolving Systems
    Publication
    • M. Jurkiewicz

    - Year 2012

    We describe the notion of Shannon Capacity for evolving channels. Furthermore, using a computer search together with some theoretical results we establish some exact values of the measure.

    Full text available to download

  • The Potential of Greed for Independence
    Publication

    - JOURNAL OF GRAPH THEORY - Year 2012

    The well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...

    Full text to download in external service

  • TreeCmp: Comparison of Trees in Polynomial Time

    Metryki filogenetyczne umożliwiają ocenę jakości wyników analizy filogenetycznej oraz wiarygodności algorytmów przeprowadzających taką analizę. Aplikacja TreeCmp oferuje efektywne, wielomianowe implementacje ośmiu takich metryk (dla drzew nieukorzenionych i zawierających korzeń) zdefiniowanych dla dowolnych filogenez (nie koniecznie binarnych). Program ten jako pierwszy umożliwia wyznaczanie nowych metryk, definiowanych w oparciu...

    Full text available to download