Department of Algorithms and Systems Modelling - Administrative Units - MOST Wiedzy


Department of Algorithms and Systems Modelling


total: 406
  • Category

  • Kind

  • Year

  • Options


  • 2019

  • A Framework for Searching in Graphs in the Presence of Errors

    - 2019

    We consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...

    Full text in external service

  • Clearing directed subgraphs by mobile agents


    We 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 S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...

    Full text in external service

  • Cztery algorytmy, które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego

    - Pismo PG - 2019

    Odcinek ten poświęcony jest problemowi programowania liniowego oraz problemowi badania liczb pierwszych.

  • Cztery algorytmy, które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie

    - Pismo PG - 2019

    W ostatniej części tryptyku poruszamy problem przyjaznego rysowania grafów oraz prezentujemy algorytmy dla szybkiego mnożenia macierzy. Nasze rozważania kończymy ilustracją postępu w dziedzinie sprzętu i oprogramowania

  • Global edge alliances in graphs

    In the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...

    Full text in external service

  • T-colorings, divisibility and circular chromatic number

    Let T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...

    Full text in external service

  • 2018


    • K. Bronk
    • D. Rutkowski
    • B. Wereszko
    • K. Wereszko
    • K. Żurek
    - Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne - 2018

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

    Full text in external service

  • Brief Announcement: Energy Constrained Depth First Search

    - 2018

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

    Full text in external service

  • Collaborative Exploration of Trees by Energy-Constrained Mobile Robots


    We study the problem of exploration of a tree by mobile agents (robots) that have limited energy. The energy constraint bounds the number of edges that can be traversed by a single agent. We use a team of agents to collectively explore the tree and the objective is to minimize the size of this team. The agents start at a single node, the designated root of the tree and the height of the tree is assumed to be less than the energy...

    Full text in external service

  • Computational aspects of greedy partitioning of graphs

    In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...

    Full text in external service

  • Connections between Mutually Unbiased Bases and Quantum Random Access Codes


    We present a new quantum communication complexity protocol, the promise--Quantum Random Access Code, which allows us to introduce a new measure of unbiasedness for bases of Hilbert spaces. The proposed measure possesses a clear operational meaning and can be used to investigate whether a specific number of mutually unbiased bases exist in a given dimension by employing Semi--Definite Programming techniques.

    Full text in external service

  • Cztery algorytmy które wstrząsnęły światem. Część I: Rys historyczny

    - Pismo PG - 2018

    Opracowanie jest pierwszym fragmentem 3-częściowego szkicu popularnonaukowego poświęconego najważniejszym osiągnięciom w dziedzinie algorytmiki teoretycznej. Wprowadzono w w arkana złożoności obliczeniowej i sztuki programowania komputerów.

  • Dynamic F-free Coloring of Graphs


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

    Full text in external service

  • Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych

    Pokazano, ż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...

  • Metody oceny jakości łączy bezprzewodowych wykorzystywanych w systemie netBaltic

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

    Full text in external service

  • Non-monotone graph searching models

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

  • On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs

    In the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.

    Full text in external service

  • On-line Search in Two-Dimensional Environment

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

    Full text in external service

  • Oxygen sensitivity of hydrogenesis’ and methanogenesis’

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

    Full text in external service

  • Pose-Invariant Face Detection by Replacing Deep Neurons with Capsules for Thermal Imagery in Telemedicine

    Abstract— The aim of this work was to examine the potential of thermal imaging as a cost-effective tool for convenient, non- intrusive remote monitoring of elderly people in different possible head orientations, without imposing specific behavior on users, e.g. looking toward the camera. Illumination and pose invariant head tracking is important for many medical applications as it can provide information, e.g. about vital signs, sensory...

  • Programowanie strukturalne

    Celem niniejszej książki jest przedstawienie wybranych metod programowania strukturalnego, tzn. takich, które prowadzą do poprawnej struktury, poprawy jakości oprogramowania oraz zwiększenia efektywności programistów. Może ona służyć jako podręcznik akademicki wykorzystywany na podstawowych kursach inżynierii oprogramowania. Zainteresuje również wszystkich tych, którzy zajmują się programowaniem amatorskim i chcą poszerzyć swoją...

    Full text in external service

  • Psychotherapy assisted with mobile applications


  • Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines


    We consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.

    Full text in external service

  • Shared processor scheduling

    We study the shared processor scheduling problem with a single shared processor to maximize total weighted overlap, where an overlap for a job is the amount of time it is processed on its private and shared processor in parallel. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an (log)-time optimization algorithm for a class...

    Full text in external service

  • Steering is an essential feature of non-locality in quantum theory

    - Nature Communications - 2018

    A physical theory is called non-local when observers can produce instantaneous effects over distant systems. Non-local theories rely on two fundamental effects: local uncertainty relations and steering of physical states at a distance. In quantum mechanics, the former one dominates the other in a well-known class of non-local games known as XOR games. In particular, optimal quantum strategies for XOR games are completely determined...

    Full text in external service

  • System information propagation for composite structures

    We study in details decoherence process of a spin register, coupled to a spin environment. We use recently developed methods of information transfer study in open quantum systems to analyze information flow between the register and its environment. We show that there are regimes when not only the register decoheres effectively to a classical bit string, but this bit string is redundantly encoded in the environment, making it available...

    Full text in external service

  • Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs


    We consider the complexity of semi-equitable k-coloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3.

  • Trade-offs in multiparty Bell-inequality violations in qubit networks

    - PHYSICAL REVIEW A - 2018

    Two overlapping bipartite binary input Bell inequalities cannot be simultaneously violated as this would contradict the usual no-signalling principle. This property is known as monogamy of Bell inequality violations and generally Bell monogamy relations refer to trade-offs between simultaneous violations of multiple inequalities. It turns out that multipartite Bell inequalities admit weaker forms of monogamies that allow for violations...

    Full text in external service

  • Turán numbers for odd wheels

    The Turán number ex(n,G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W_n is a graph on n vertices obtained from a C_{n−1} by adding one vertex w and making w adjacent to all vertices of the C_{n−1}. We obtain two exact values for small wheels: ex(n,W_5)=\lfloor n^2/4+n/2\rfloor, ex(n,W_7)=\lfloor n^2/4+n/2+1 \rfloor. Given that ex(n,W_6) is already known, this...

    Full text in external service

  • 2017

  • Approximation Strategies for Generalized Binary Search in Weighted Trees

    - 2017

    We consider the following generalization of the binary search problem. A search strategy is required to locate an unknown target node t in a given tree T. Upon querying a node v of the tree, the strategy receives as a reply an indication of the connected component of T\{v} containing the target t. The cost of querying each node is given by a known non-negative weight function, and the considered objective is to minimize the total...

    Full text in external service

  • Average distance is submultiplicative and subadditive with respect to the strong product of graphs

    We show that the average distance is submultiplicative and subadditive on the set of non-trivial connected graphs with respect to the strong product. We also give an application of the above-mentioned result.

    Full text in external service

  • Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots

    - 2017

    We study two variants of delivery problems for mobile robots sharing energy. Each mobile robot can store at any given moment at most two units of energy, and whenever two robots are at the same location, they can transfer energy between each other, respecting the maximum capacity. The robots operate in a simple graph and initially each robot has two units of energy. A single edge traversal by an robot reduces its energy by one...

    Full text in external service

  • Collision-free network exploration

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

    Mobile agents start at different nodes of an n-node network. The agents synchronously move along the network edges in a collision-free way, i.e., in no round two agents may occupy the same node. An agent has no knowledge of the number and initial positions of other agents. We are looking for the shortest time required to reach a configuration in which each agent has visited all nodes and returned to its starting location. In...

    Full text in external service

  • Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions


    Ability to quantify dissimilarity of different phylogenetic trees describing the relationship between the same group of taxa is required in various types of phylogenetic studies. For example, such metrics are used to assess the quality of phylogeny construction methods, to define optimization criteria in supertree building algorithms, or to find horizontal gene transfer (HGT) events. Among the set of metrics described so far in...

    Full text in external service

  • Complementarity between entanglement-assisted and quantum distributed random access code

    - PHYSICAL REVIEW A - 2017

    Collaborative communication tasks such as random access codes (RACs) employing quantum resources have manifested great potential in enhancing information processing capabilities beyond the classical limitations. The two quantum variants of RACs, namely, quantum random access code (QRAC) and the entanglement-assisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific...

    Full text in external service

  • Equitable coloring of corona multiproducts of graphs

    - Discussiones Mathematicae Graph Theory - 2017

    We give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.

  • Gdańska Międzynarodowa Szkoła Letnia na WETI

    - Pismo PG - 2017

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

  • Interval incidence coloring of subcubic graphs

    In this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.

    Full text in external service

  • Monitoring of the Process of System Information Broadcasting in Time

    One of the problems of quantum physics is how a measurement turns quantum, noncopyable data, towards copyable classical knowledge. We use the quantum state discrimination in a central system model to show how its evolution leads to the broadcasting of the information, and how orthogonalization and decoherence factors allow us to monitor the distance of the state in question to the one perfectly broadcasting information, in any...

    Full text in external service

  • No-Wait & No-Idle Open Shop Minimum Makespan Scheduling with Bioperational Jobs

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

    Full text available

  • On Computational Aspects of Greedy Partitioning of Graphs

    - 2017

    In this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...

    Full text in external service

  • Realizacja zadań w grafie przez grupę mobilnych jednostek

    - 2017

    Grupa 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),...

    Full text available

  • Restricted open shop scheduling

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

    Full text in external service

  • Równowaga strategiczna dla zbiorów defensywnych w drzewach

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

    Full text in external service

  • Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments

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

    Full text in external service

  • Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines

    The problem of scheduling n identical jobs on 4 uniform machines with speeds s1>=s2>=s3>=s4 is considered.The aim is to find a schedule with minimum possible length. We assume that jobs are subject to mutual exclusion constraints modeled by a bipartite incompatibility graph of degree delta. We show that the general problem is NP-hard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to...

    Full text in external service

  • Shared multi-processor scheduling

    We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job’s completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized...

    Full text in external service

  • Szeregowanie zadań dwuprocesorowych w systemach otwartych

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

    Full text in external service

  • Szybkość przeszukiwania grafu

    - 2017

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

  • The Snow Team Problem

    - 2017

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

    Full text in external service