# Katedra Algorytmów i Modelowania Systemów

## Publikacje

• wyników na stronę:
• rok:
tytuł:

wszystkich: 396

## Katalog

• ### 2016

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

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 • #### 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 • #### 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 • #### 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. • #### 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 • #### 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 • #### 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 • #### 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... • #### 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 • ### 2015 • #### 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 • #### 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.... • #### 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 • #### 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 • #### 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 • #### 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 • #### 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 • #### 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 • #### 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 • #### 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 • #### Fast collaborative graph exploration D. Dereniowski, Y. Disser, A. Kosowski, D. Pająk, P. Uznański - INFORMATION AND COMPUTATION - 2015 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 • #### Graph security testing Set S ⊂ V is called secure set iff ∀ X ⊂ S | N [ X ] ∩ S | ≥ | N ( X ) \ S | [3]. That means that every subset of a secure set has at least as many friends (neighbour vertices in S) as enemies (neighbour vertices outside S) and will be defended in case of attack. Problem of determining if given set is secure is co −NP -complete, there is no efficient algorithm solving it [3]. Property testers are algorithms that distinguish inputs... • Pełny tekst w serwisie zewnętrznym • #### Interval incidence graph coloring In this paper we introduce a concept of interval incidence coloring of graphs and survey its general properties including lower and upper bounds on the number of colors. Our main focus is to determine the exact value of the interval incidence coloring number χii for selected classes of graphs, i.e. paths, cycles, stars, wheels, fans, necklaces, complete graphs and complete k-partite graphs. We also study the complexity of the... • Pełny tekst w serwisie zewnętrznym • #### KOALA Graph Theory Internet Service KOALA has been created with the idea of C++ library templates, implementing a broad set of procedures in the fields of algorithmic graph theory and network problems in discreate optimization. During the C2NIWA project, a library has been greatly ectended, the code refactored and enclosed with the internet service available in the public repository of thr project. Today it contains interconnected educational materials in the form... • Pełny tekst w serwisie zewnętrznym • #### Minimum order of graphs with given coloring parameters G. Bacsó, P. Borowiecki, M. Hujter, Z. Tuza - DISCRETE MATHEMATICS - 2015 A complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),... • Pełny tekst w serwisie zewnętrznym • #### New potential functions for greedy independence and coloring A potential function$f_G$of a finite, simple and undirected graph$G=(V,E)$is an arbitrary function$f_G : V(G) \rightarrow \mathbb{N}_0$that assigns a nonnegative integer to every vertex of a graph$G$. In this paper we define the iterative process of computing the step potential function$q_G$such that$q_G(v)\leq d_G(v)$for all$v\in V(G)$. We use this function in the development of new Caro-Wei-type and Brooks-type... • Pełny tekst w serwisie zewnętrznym • #### On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral J. Dybizbański, T. Dzido, S. Radziszowski - ARS COMBINATORIA - 2015 The Zarankiewicz number z ( m, n ; s, t ) is the maximum number of edges in a subgraph of K m,n that does not contain K s,t as a subgraph. The bipartite Ramsey number b ( n 1 , · · · , n k ) is the least positive integer b such that any coloring of the edges of K b,b with k colors will result in a monochromatic copy of K n i ,n i in the i -th color, for some i , 1 ≤ i ≤ k . If n i = m for all i , then we denote this number by b k ( m ).... • #### On the independence number of some strong products of cycle-powers In the paper we give some theoretical and computational results on the third strong power of cycle-powers, for example, we have found the independence numbers alpha((C^2_10)^⊠3) = 30 and alpha((C^4 _14)^⊠3) = 14. A number of optimizations have been introduced to improve the running time of our exhaustive algorithm used to establish the independence number of the third strong power of cycle-powers. Moreover, our results establish... • Pełny tekst w serwisie zewnętrznym • #### On trees attaining an upper bound on the total domination number A total 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. The total domination number of a graph G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. Chellali and Haynes [Total and paired-domination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 69-75] established the following upper bound on the total domination... • Pełny tekst w serwisie zewnętrznym • #### On trees with equal 2-domination and 2-outer-independent domination numbers For a graph G = (V,E), a subset D \subseteq V(G) is a 2-dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2-outer-independent dominating set if additionally the set V(G)\D is independent. The 2-domination (2-outer-independent domination, respectively) number of G, is the minimum cardinality of a 2-dominating (2-outer-independent dominating, respectively) set of G. We characterize all trees...
• Pełny tekst w serwisie zewnętrznym
• #### On trees with equal domination and total outer-independent domination numbers

For a graph G=(V,E), a subset D subseteq V(G) is a dominating set if every vertex of V(G)D has a neighbor in D, while it is a total outer-independent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outer-independent domination, respectively) number of G is the minimum cardinality of a dominating (total outer-independent dominating, respectively) set of G. We characterize...
• #### Optimal backbone coloring of split graphs with matching backbones

For a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
• Pełny tekst w serwisie zewnętrznym
• #### Rendezvous of heterogeneous mobile agents in edge-weighted networks

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
• #### Robust amplification of Santha-Vazirani sources with three devices

P. Mironowicz, R. Gallego, M. Pawłowski - PHYSICAL REVIEW A - 2015
We demonstrate that amplification of arbitrarily weak randomness is possible using quantum resources. We present a randomness amplification protocol that involves Bell experiments. We find a Bell inequality which can amplify arbitrarily weak randomness and give a detailed analysis of the protocol involving it. Our analysis includes finding a sufficient violation of Bell inequality as a function of the initial quality of randomness....
• Pełny tekst w serwisie zewnętrznym
• #### The Backbone Coloring Problem for Bipartite Backbones

Let G be a simple graph, H be its spanning subgraph and λ≥2 be an integer. By a λ -backbone coloring of G with backbone H we mean any function c that assigns positive integers to vertices of G in such a way that |c(u)−c(v)|≥1 for each edge uv∈E(G) and |c(u)−c(v)|≥λ for each edge uv∈E(H) . The λ -backbone chromatic number BBCλ(G,H) is the smallest integer k such that there exists a λ -backbone coloring c of G with backbone H satisfying...
• Pełny tekst w serwisie zewnętrznym
• #### The complexity of minimum-length path decompositions

We consider a bi-criteria generalization of the pathwidth problem, where, for given integers k, l and a graph G, we ask whether there exists a path decomposition P of G such that the width of P is at most k and the number of bags in P, i.e., the length of P, is at most l. We provide a complete complexity classiﬁcation of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is ﬁxed-parameter...
• Pełny tekst w serwisie zewnętrznym
• #### The complexity of zero-visibility cops and robber

D. Dereniowski, D. Dyer, R. Tifenbach, B. Yang - THEORETICAL COMPUTER SCIENCE - 2015
We consider the zero-visibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zero-visibility Cops and Robber game. We present a heavily modified version of an already-existing algorithm that computes the zero-visibility copnumber of a tree in linear time and we show that the corresponding decision problem is NP-complete on a nontrivial...
• Pełny tekst w serwisie zewnętrznym
• #### The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

Given a graph G, a spanning subgraph H of G and an integer λ>=2, a λ-backbone coloring of G with backbone H is a vertex coloring of G using colors 1, 2, ..., in which the color difference between vertices adjacent in H is greater than or equal to lambda. The backbone coloring problem is to find such a coloring with maximum color that does not exceed a given limit k. In this paper, we study the backbone coloring problem for bounded-degree...
• Pełny tekst w serwisie zewnętrznym
• #### The computational complexity of the backbone coloring problem for planar graphs with connected backbones

In the paper we study the computational complexity of the backbone coloring problem for planar graphs with connected backbones. For every possible value of integer parameters λ≥2 and k≥1 we show that the following problem: Instance: A simple planar graph GG, its connected spanning subgraph (backbone) HH. Question: Is there a λ-backbone coloring c of G with backbone H such that maxc(V(G))≤k? is either NP-complete or polynomially...
• Pełny tekst w serwisie zewnętrznym
• #### The searchlight problem for road networks

D. Dereniowski, H. Ono, I. Suzuki, Ł. Wrona, M. Yamashita, P. Żyliński - 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

D. Dereniowski, D. Dyer, R. Tifenbach, B. Yang - 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

M. Jurkiewicz - 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

D. Dereniowski, A. Kosowski, D. Pająk, P. Uznański - 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

B. Krishnakumari, Y. Venkatakrishnan, M. Krzywkowski - 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