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

Wyszukiwarka

Katedra Algorytmów i Modelowania Systemów

Filtry

wszystkich: 406
  • Kategoria

  • Typ

  • Rok

  • Opcje

Katalog

  • 2015

  • The searchlight problem for road networks

    - THEORETICAL COMPUTER SCIENCE - 2015

    We consider the problem of searching for a mobile intruder hiding in a road network given as the union of two or more lines, or two or more line segments, in the plane. Some of the intersections of the road network are occupied by stationary guards equipped with a number of searchlights, each of which can emit a single ray of light in any direction along the lines (or line segments) it is on. The goal is to detect the intruder,...

    Pełny tekst w serwisie zewnętrznym

  • Towards the boundary between easy and hard control problems in multicast Clos networks

    In this article we study 3-stage Clos networks with multicast calls in general and 2-cast calls, in particular. We investigate various sizes of input and output switches and discuss some routing problems involved in blocking states. To express our results in a formal way we introduce a model of hypergraph edge-coloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially...

    Pełny tekst w serwisie zewnętrznym

  • Zero-visibility cops and robber and the pathwidth of a graph

    - JOURNAL OF COMBINATORIAL OPTIMIZATION - 2015

    We examine the zero-visibility cops and robber graph searching model, which differs from the classical cops and robber game in one way: the robber is invisible. We show that this model is not monotonic. We show that the zero-visibility copnumber of a graph is bounded above by its pathwidth and cannot be bounded below by any nontrivial function of the pathwidth. As well, we define a monotonic version of this game and show that the...

    Pełny tekst w serwisie zewnętrznym

  • 2014

  • A survey on known values and bounds on the Shannon capacity

    - 2014

    In this survey we present exact values and bounds on the Shannon capacity for different classes of graphs, for example for regular graphs and Kneser graphs. Additionally, we show a relation between Ramsey numbers and Shannon capacity.

    Pełny tekst w serwisie zewnętrznym

  • Algorithms for testing security in graphs

    In this paper we propose new algorithmic methods giving with the high probability the correct answer to the decision problem of security in graphs. For a given graph G and a subset S of a vertex set of G we have to decide whether S is secure, i.e. every subset X of S fulfils the condition: |N[X] \cap S| >= |N[X] \ S|, where N[X] is a closed neighbourhood of X in graph G. We constructed a polynomial time property pseudotester based...

  • An algorithm for listing all minimal double dominating sets of a tree

    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.

    Pełny tekst w serwisie zewnętrznym

  • Bounds on the Cover Time of Parallel Rotor Walks

    - 2014

    The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...

    Pełny tekst w serwisie zewnętrznym

  • Bounds on the vertex-edge domination number of a tree

    - COMPTES RENDUS MATHEMATIQUE - 2014

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

  • Brushing with additional cleaning restrictions

    In graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...

    Pełny tekst w serwisie zewnętrznym

  • Collision-Free Network Exploration

    • J. Czyzowicz
    • D. Dereniowski
    • L. Gąsieniec
    • R. Klasing
    • A. Kosowski
    • D. Pająk
    - 2014

    A set of mobile agents is placed at different nodes of a n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round may two agents occupy the same node. In each round, an agent may choose to stay at its currently occupied node or to move to one of its neighbors. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest possible...

    Pełny tekst w serwisie zewnętrznym

  • 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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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

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

    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

    - 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

    - 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

    - 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

    - 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

    - 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

    - 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