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

Wyszukiwarka

Katedra Algorytmów i Modelowania Systemów

Filtry

wszystkich: 396
  • Kategoria

  • Typ

  • Rok

  • Opcje

Katalog

  • 2018

  • ANALIZA MOŻLIWOŚCI WYKORZYSTANIA TRANSFORMACJI FALKOWEJ DO DETEKCJI NIEZAJĘTYCH PASM CZĘSTOTLIWOŚCI

    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.
    • Pełny tekst w serwisie zewnętrznym
  • Brief Announcement: Energy Constrained Depth First Search

    D. Shantanu, D. Dereniowski, P. Uznański - 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...
    • Pełny tekst w serwisie zewnętrznym
  • Collaborative Exploration of Trees by Energy-Constrained Mobile Robots

    S. Das, D. Dereniowski, C. Karousatou - THEORY OF COMPUTING SYSTEMS - 2018
    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...
    • Pełny tekst w serwisie zewnętrznym
  • 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...
    • Pełny tekst w serwisie zewnętrznym
  • Connections between Mutually Unbiased Bases and Quantum Random Access Codes

    E. Aguilar Lozano, J. Borkała, P. Mironowicz, M. Pawłowski, - PHYSICAL REVIEW LETTERS - 2018
    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.
    • Pełny tekst w serwisie zewnętrznym
  • Dynamic F-free Coloring of Graphs

    P. Borowiecki, E. Sidorowicz - GRAPHS AND COMBINATORICS - 2018
    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...
    • Pełny tekst w serwisie zewnętrznym
  • 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...
    • Pełny tekst w serwisie zewnętrznym
  • 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.
    • Pełny tekst w serwisie zewnętrznym
  • 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:...
    • Pełny tekst w serwisie zewnętrznym
  • 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%.
    • Pełny tekst w serwisie zewnętrznym
  • Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines

    H. Furmańczyk, M. Kubale - DISCRETE APPLIED MATHEMATICS - 2018
    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.
    • Pełny tekst w serwisie zewnętrznym
  • 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...
    • Pełny tekst w serwisie zewnętrznym
  • Steering is an essential feature of non-locality in quantum theory

    R. Ramanathan, D. Goyeneche, S. Muhammad, P. Mironowicz, M. Grünfeld, M. Bourennane, P. Horodecki - 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...
    • Pełny tekst w serwisie zewnętrznym
  • 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...
    • Pełny tekst w serwisie zewnętrznym
  • Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

    H. Furmańczyk, M. Kubale - DISCRETE APPLIED MATHEMATICS - 2018
    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

    R. Ramanathan, P. Mironowicz - 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...
    • Pełny tekst w serwisie zewnętrznym
  • 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...
    • Pełny tekst w serwisie zewnętrznym
  • 2017

  • Approximation Strategies for Generalized Binary Search in Weighted Trees

    D. Dereniowski, A. Kosowski, P. Uznański, M. Zou - 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...
    • Pełny tekst w serwisie zewnętrznym