Wyszukiwarka
Katedra Algorytmów i Modelowania Systemów
Publikacje
Filtry
wszystkich: 517
Katalog Publikacji
Rok 2019
-
Potyczki algorytmiczne, czyli Alicja i Bogdan w różnych sytuacjach. Alicja i Bogdan otrzymują spadek
PublikacjaWprowadzono w zagadnienie drzewa Steinera na płaszczyźnie
-
On-line Search in Two-Dimensional Environment
PublikacjaWe 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. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublikacjaIn this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...
-
Improving Accuracy of Contactless Respiratory Rate Estimation by Enhancing Thermal Sequences with Deep Neural Networks
PublikacjaEstimation of vital signs using image processing techniques have already been proved to have a potential for supporting remote medical diagnostics and replacing traditional measurements that usually require special hardware and electrodes placed on a body. In this paper, we further extend studies on contactless Respiratory Rate (RR) estimation from extremely low resolution thermal imagery by enhancing acquired sequences using Deep...
-
Global edge alliances in graphs
PublikacjaIn 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...
-
Gdańska Międzynarodowa Szkoła Letnia na WETI
PublikacjaW dniach 6-12 lipca 2019 roku Katedra Algorytmów i Modelowania Systemów zorganizowała 3. Międzynarodową Szkołę Letnią poświęconą algorytmom dla problemów optymalizacji dyskretnej.
-
Finding small-width connected path decompositions in polynomial time
PublikacjaA connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers...
-
Experimentally feasible semi-device-independent certification of four-outcome positive-operator-valued measurements
PublikacjaRecently the quantum information science community devoted a lot of attention to the theoretical and practical aspects of generalized measurements, the formalism of all possible quantum operations leading to acquisition of classical information. On the other hand, due to imperfections present in quantum devices, and limited thrust to them, a trend of formulating quantum information tasks in a semi-device-independent manner emerged....
-
Equitable coloring of hypergraphs
PublikacjaA hypergraph is equitablyk-colorable if its vertices can be partitioned into k sets/colorclasses in such a way that monochromatic edges are avoided and the number of verticesin any two color classes differs by at most one. We prove that the problem of equitable 2-coloring of hypergraphs is NP-complete even for 3-uniform hyperstars. Finally, we apply the method of dynamic programming for designing a polynomial-time algorithm to...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublikacjaA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
Cztery algorytmy, które wstrząsnęły światem. Część III: Sprzęt czy oprogramowanie
PublikacjaW 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
-
Cztery algorytmy, które wstrząsnęły światem. Część II: Od czasu wykładniczego do wielomianowego
PublikacjaOdcinek ten poświęcony jest problemowi programowania liniowego oraz problemowi badania liczb pierwszych.
-
Cops, a fast robber and defensive domination on interval graphs
PublikacjaThe game of Cops and ∞-fast Robber is played by two players, one controlling c cops, the other one robber. The players alternate in turns: all the cops move at once to distance at most one each, the robber moves along any cop-free path. Cops win by sharing a vertex with the robber, the robber by avoiding capture indefinitely. The game was proposed with bounded robber speed by Fomin et al. in “Pursuing a fast robber on a graph”,...
-
Clearing directed subgraphs by mobile agents
PublikacjaWe 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...
-
Building a Nest by an Automaton
PublikacjaA robot modeled as a deterministic finite automaton has to build a structure from material available to it. The robot navigates in the infinite oriented grid $Z x Z$. Some cells of the grid are full (contain a brick) and others are empty. The subgraph of the grid induced by full cells, called the {\em field}, is initially connected. The (Manhattan) distance between the farthest cells of the field is called its {\em span}. The robot...
-
Better polynomial algorithms for scheduling unit-length jobs with bipartite incompatibility graphs on uniform machines
PublikacjaThe goal of this paper is to explore and to provide tools for the investigation of the problems of unit-length scheduling of incompatible jobs on uniform machines. We present two new algorithms that are a significant improvement over the known algorithms. The first one is Algorithm 2 which is 2-approximate for the problem Qm|p j = 1, G = bisubquartic|Cmax . The second one is Algorithm 3 which is 4-approximate for the problem Qm|p...
-
A Framework for Searching in Graphs in the Presence of Errors
PublikacjaWe 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...
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
Rok 2018
-
Turán numbers for odd wheels
PublikacjaThe 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...
-
Trade-offs in multiparty Bell-inequality violations in qubit networks
PublikacjaTwo 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...
-
Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs
PublikacjaWe 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.
-
System information propagation for composite structures
PublikacjaWe 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...
-
Steering is an essential feature of non-locality in quantum theory
PublikacjaA 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...
-
Shared processor scheduling
PublikacjaWe 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...
-
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
PublikacjaWe 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.
-
Psychotherapy assisted with mobile applications
Publikacja.
-
Programowanie strukturalne
PublikacjaCelem 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ą...
-
Pose-Invariant Face Detection by Replacing Deep Neurons with Capsules for Thermal Imagery in Telemedicine
PublikacjaAbstract— 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...
-
Oxygen sensitivity of hydrogenesis’ and methanogenesis’
PublikacjaIn 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%.
-
On-line Search in Two-Dimensional Environment
PublikacjaWe 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:...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublikacjaIn 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.
-
Non-monotone graph searching models
PublikacjaGraph 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...
-
Metody oceny jakości łączy bezprzewodowych wykorzystywanych w systemie netBaltic
PublikacjaPrzedstawiono 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...
-
Jak transportować produkty chemiczne, czyli przypadek wsadowego szeregowania zadań kompatybilnych
PublikacjaPokazano, ż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...
-
Dynamic F-free Coloring of Graphs
PublikacjaA 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...
-
Cztery algorytmy które wstrząsnęły światem. Część I: Rys historyczny
PublikacjaOpracowanie 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.
-
Connections between Mutually Unbiased Bases and Quantum Random Access Codes
PublikacjaWe 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.
-
Computational aspects of greedy partitioning of graphs
PublikacjaIn 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...
-
Collaborative Exploration of Trees by Energy-Constrained Mobile Robots
PublikacjaWe 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...
-
Brief Announcement: Energy Constrained Depth First Search
PublikacjaDepth 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...
-
ANALIZA MOŻLIWOŚCI WYKORZYSTANIA TRANSFORMACJI FALKOWEJ DO DETEKCJI NIEZAJĘTYCH PASM CZĘSTOTLIWOŚCI
PublikacjaCelem 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.
Rok 2017
-
The Snow Team Problem
PublikacjaWe 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)...
-
Szybkość przeszukiwania grafu
PublikacjaPrzeszukiwanie 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ą...
-
Szeregowanie zadań dwuprocesorowych w systemach otwartych
PublikacjaW 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ć...
-
Shared multi-processor scheduling
PublikacjaWe 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...
-
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
PublikacjaThe 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...
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublikacjaWe consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard,...
-
Równowaga strategiczna dla zbiorów defensywnych w drzewach
PublikacjaW 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...
-
Restricted open shop scheduling
PublikacjaIn 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)....
-
Realizacja zadań w grafie przez grupę mobilnych jednostek
PublikacjaGrupa 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),...