# Katedra Algorytmów i Modelowania Systemów

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

4. ## 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
5. ## 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.
• Pełny tekst w serwisie zewnętrznym
6. ## Collaborative Delivery by Energy-Sharing Low-Power Mobile Robots

E. Bampas, S. Das, D. Dereniowski, C. Karousatou - 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...
• Pełny tekst w serwisie zewnętrznym
7. ## Collision-free network exploration

J. Czyzowicz, D. Dereniowski, L. Gąsieniec, R. Klasing, A. Kosowski, D. Pająk - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - 2017
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...
• Pełny tekst w serwisie zewnętrznym
8. ## Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions

D. Bogdanowicz, K. Giaro - JOURNAL OF COMPUTATIONAL BIOLOGY - 2017
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...
• Pełny tekst w serwisie zewnętrznym
9. ## Complementarity between entanglement-assisted and quantum distributed random access code

A. Hameedi, D. Saha, P. Mironowicz, M. Pawłowski, M. Bourennane - 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...
• Pełny tekst w serwisie zewnętrznym
10. ## 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
11. ## Equitable coloring of corona multiproducts of graphs

H. Furmańczyk, M. Kubale, V. Mkrtchyan - 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.
12. ## 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...
• Pełny tekst w serwisie zewnętrznym
13. ## 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...
• Pełny tekst w serwisie zewnętrznym
14. ## On Computational Aspects of Greedy Partitioning of Graphs

P. Borowiecki - 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...
• Pełny tekst w serwisie zewnętrznym
15. ## Realizacja zadań w grafie przez grupę mobilnych jednostek

D. Osula - 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),...
• Pełny tekst w portalu
16. ## Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experoments

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,...
• Pełny tekst w serwisie zewnętrznym
17. ## 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...
• Pełny tekst w serwisie zewnętrznym
18. ## 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...
• Pełny tekst w serwisie zewnętrznym
19. ## 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ć...
• Pełny tekst w serwisie zewnętrznym
20. ## Szybkość przeszukiwania grafu

R. Ostrowski - 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ą...
21. ## The Snow Team Problem

D. Dereniowski, A. Lingas, M. Persson, D. Osula, P. Żyliński - 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)...
• Pełny tekst w serwisie zewnętrznym

23. ## An O ( n log n ) algorithm for finding edge span of cacti

Let G=(V,E) be a nonempty graph and xi be a function. In the paper we study the computational complexity of the problem of finding vertex colorings c of G such that: (1) |c(u)-c(v)|>=xi(uv) for each edge uv of E; (2) the edge span of c, i.e. max{|c(u)-c(v)|: uv belongs to E}, is minimal. We show that the problem is NP-hard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for...
• Pełny tekst w serwisie zewnętrznym
24. ## Applications of semi-definite optimization in quantum information protocols

P. Mironowicz - 2016
This work is concerned with the issue of applications of the semi-definite programming (SDP) in the field of quantum information sci- ence. Our results of the analysis of certain quantum information protocols using this optimization technique are presented, and an implementation of a relevant numerical tool is introduced. The key method used is NPA discovered by Navascues et al. [Phys. Rev. Lett. 98, 010401 (2007)]. In chapter...
25. ## Bounds on the cover time of parallel rotor walks

D. Dereniowski, A. Kosowski, D. Pająk, P. Uznański - JOURNAL OF COMPUTER AND SYSTEM SCIENCES - 2016
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 successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider...
• Pełny tekst w serwisie zewnętrznym
26. ## Distributed Evacuation in Graphs with Multiple Exits

We consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy...
• Pełny tekst w serwisie zewnętrznym
27. ## Edge-coloring of 3-uniform hypergraphs

We consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
• Pełny tekst w serwisie zewnętrznym
28. ## Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G. In this paper the problem of determinig the equitable coloring number for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas...
• Pełny tekst w serwisie zewnętrznym
29. ## Equitable coloring of graphs. Recent theoretical results and new practical algorithms

In this paper we survey recent theoretical results concerning conditions for equitable colorability of some graphs and recent theoretical results concerning the complexity of equitable coloring problem. Next, since the general coloring problem is strongly NP-hard, we report on practical experiments with some efficient polynomial-time algorithms for approximate equitable coloring of general graphs.
• Pełny tekst w serwisie zewnętrznym
30. ## Global defensive sets in graphs

In the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
• Pełny tekst w serwisie zewnętrznym
31. ## Increased Certification of Semi-device Independent Random Numbers using Many Inputs and More Postprocessing

P. Mironowicz, A. Tavakoli, A. Hameedi, B. Marques, M. Pawłowski, M. Bourennane - NEW JOURNAL OF PHYSICS - 2016
Quantum communication with systems of dimension larger than two provides advantages in information processing tasks. Examples include higher rates of key distribution and random number generation. The main disadvantage of using such multi-dimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a not-so-obvious problem: the relation between randomness certification and computational requirements...
• Pełny tekst w serwisie zewnętrznym
32. ## Independence in uniform linear triangle-free hypergraphs

P. Borowiecki, M. Gentner, C. Löwenstein, D. Rautenbach - DISCRETE MATHEMATICS - 2016
The independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
• Pełny tekst w serwisie zewnętrznym
33. ## Lossless Compression of Binary Trees with Correlated Vertex Names

A. Manager, K. Turowski, W. Szpankowski - 2016
Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering...
• Pełny tekst w serwisie zewnętrznym
34. ## Network Graph Transformation Providing Fast Calculation of Paths for Resilient Routing

Protection of transmission against failures can be appropriately dealt with by alternative paths. However, common schemes (e.g., Bhandaris scheme) are characterized by a remarkable delay while determining the transmission paths. This in turn may have a serious impact on serving dynamic demands (characterized by relatively short duration time). As a remedy to this problem, we introduce an approach to pre-compute the sets of disjoint...
35. ## Non-isolating bondage in graphs

A dominating set of a graph $G = (V,E)$ is a set $D$ of vertices of $G$ such that every vertex of $V(G) \setminus D$ has a neighbor in $D$. The domination number of a graph $G$, denoted by $\gamma(G)$, is the minimum cardinality of a dominating set of $G$. The non-isolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(G-E') \ge 1$ and $\gamma(G-E')... • Pełny tekst w serwisie zewnętrznym 36. ## Normal-form preemption sequences for an open problem in scheduling theory B. Chen, E. Coffman, D. Dereniowski, W. Kubiak - JOURNAL OF SCHEDULING - 2016 Structural properties of optimal preemptive schedules have been studied in a number of recent papers with a primary focus on two structural parameters: the minimum number of preemptions necessary, and a tight lower bound on shifts, i.e., the sizes of intervals bounded by the times created by preemptions, job starts, or completions. These two parameters have been investigated for a large class of preemptive scheduling problems,... • Pełny tekst w serwisie zewnętrznym 37. ## On bipartization of cubic graphs by removal of an independent set H. Furmańczyk, M. Kubale, S. Radziszowski - DISCRETE APPLIED MATHEMATICS - 2016 We study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set. • Pełny tekst w serwisie zewnętrznym 38. ## On some open questions for Ramsey and Folkman numbers S. Radziszowski, X. Xiaodong - 2016 We discuss some of our favorite open questions about Ramsey numbers and a related problem on edge Folkman numbers. For the classical two-color Ramsey numbers, we first focus on constructive bounds for the difference between consecutive Ramsey numbers. We present the history of progress on the Ramsey number R(5,5) and discuss the conjecture that it is equal to 43. 39. ## On the hardness of computing span of subcubic graphs In the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used. • Pełny tekst w serwisie zewnętrznym 40. ## Sharp bounds for the complexity of semi-equitable coloring of cubic and subcubic graphs M. Kubale, H. Furmańczyk - 2016 In this paper we consider the complexity of semi-equitable k-coloring of the vertices of a cubic or subcubic graph. We show that, given n-vertex subcubic graph G, a semi-equitable k-coloring of G is NP-hard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring. • Pełny tekst w serwisie zewnętrznym 41. ## Strategic balance in graphs For a given graph G, a nonempty subset S contained in V ( G ) is an alliance iff for each vertex v ∈ S there are at least as many vertices from the closed neighbourhood of v in S as in V ( G ) − S. An alliance is global if it is also a dominating set of G. The alliance partition number of G was defined in Hedetniemi et al. (2004) to be the maximum number of sets in a partition of V ( G ) such that each set is an alliance. Similarly,... • Pełny tekst w serwisie zewnętrznym 42. ## Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów M. Kubale - 2016 Rozważono problem szeregowania n zadań jednostkowych na 4 procesorach jednorodnych o szybkościach s1>=s2>=s3>=s4. Celem szeregowania jest utworzenie najkrótszego możliwego harmonogramu. Zadania podlegają ograniczeniom zasobowym mówiącym, że niektóre pary zadań nie mogą być wykonane na tym samym procesorze. Podajemy algorytm dokładny, który rozwiązuje problem w czasie liniowym, o ile graf niezgodności jest kubiczny. Ponadto podajemy... 43. ## Topology recognition and leader election in colored networks Topology recognition and leader election are fundamental tasks in distributed computing in networks. The first of them requires each node to find a labeled isomorphic copy of the network, while the result of the second one consists in a single node adopting the label 1 (leader), with all other nodes adopting the label 0 and learning a path to the leader. We consider both these problems in networks whose nodes are equipped with... • Pełny tekst w serwisie zewnętrznym 44. ### 2015 45. ## 2-outer-independent domination in graphs We initiate the study of 2-outer-independent domination in graphs. A 2-outer-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)\D has at least two neighbors in D, and the set V(G)\D is independent. The 2-outer-independent domination number of a graph G is the minimum cardinality of a 2-outer-independent dominating set of G. We show that if a graph has minimum degree at least two,... • Pełny tekst w serwisie zewnętrznym 46. ## A bound on the number of middle-stage crossbars in f-cast rearrangeable Clos networks In 2006 Chen and Hwang gave a necessary and sufficient condition under which a three-stage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fan-out property, we give similar conditions for f-cast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. high-speed crossconnects.... 47. ## A Task-Scheduling Approach for Efficient Sparse Symmetric Matrix-Vector Multiplication on a GPU In this paper, a task-scheduling approach to efficiently calculating sparse symmetric matrix-vector products and designed to run on Graphics Processing Units (GPUs) is presented. The main premise is that, for many sparse symmetric matrices occurring in common applications, it is possible to obtain significant reductions in memory usage and improvements in performance when the matrix is prepared in certain ways prior to computation.... • Pełny tekst w serwisie zewnętrznym 48. ## An upper bound for 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 γ_d^{oi}(G), is the minimum cardinality of a double outer-independent dominating set of G. We prove... • Pełny tekst w serwisie zewnętrznym 49. ## Bipartite theory of graphs: outer-independent domination Let$G = (V,E)$be a bipartite graph with partite sets$X$and$Y$. Two vertices of$X$are$X$-adjacent if they have a common neighbor in$Y$, and they are$X$-independent otherwise. A subset$D \subseteq X$is an$X$-outer-independent dominating set of$G$if every vertex of$X \setminus D$has an$X$-neighbor in$D$, and all vertices of$X \setminus D$are pairwise$X$-independent. The$X\$-outer-independent domination number...
• Pełny tekst w serwisie zewnętrznym
50. ## Deterministic Rendezvous in Restricted Graphs

A. Farrugia, L. Gąsieniec, Ł. Kuszner, E. Pacheco - 2015
In this paper we consider the problem of synchronous rendezvous in which two anonymous mobile entities (robots) A and B are expected to meet at the same time and point in a graph G = (V;E). Most of the work devoted to rendezvous in graphs assumes that robots have access to the same sets of nodes and edges, where the topology of connections may be initially known or unknown. In our work we assume the movement of robots is restricted...
• Pełny tekst w serwisie zewnętrznym
51. ## Device-independent quantum key distribution based on measurement inputs

R. Rahaman, M. Parker, P. Mironowicz, M. Pawłowski - PHYSICAL REVIEW A - 2015
We provide an analysis of a family of device-independent quantum key distribution (QKD) protocols that has the following features. (a) The bits used for the secret key do not come from the results of the measurements on an entangled state but from the choices of settings. (b) Instead of a single security parameter (a violation of some Bell inequality) a set of them is used to estimate the level of trust in the secrecy of the key....
• Pełny tekst w serwisie zewnętrznym
52. ## Distinguishing views in symmetric networks: A tight lower bound

The view of a node in a port-labeled network is an infinite tree encoding all walks in the network originating from this node. We prove that for any integers n ≥ D ≥ 1, there exists a port-labeled network with at most n nodes and diameter at most D which contains a pair of nodes whose (infinite) views are different, but whose views truncated to depth Omega( D log(n/ D )) are identical.
• Pełny tekst w serwisie zewnętrznym
53. ## Distributed graph searching with a sense of direction

In this work we consider the edge searching problem for vertex-weighted graphs with arbitrarily fast and invisible fugitive. The weight function w provides for each vertex v the minimum number of searchers required to guard v, i.e., the fugitive may not pass through v without being detected only if at least w(v) searchers are present at v. This problem is a generalization of the classical edge searching problem, in which one has...
• Pełny tekst w serwisie zewnętrznym
54. ## Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP- complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize...
• Pełny tekst w serwisie zewnętrznym