Katedra Algorytmów i Modelowania Systemów
Publikacje
Filtry
wszystkich: 396
Katalog

2018

ANALIZA MOŻLIWOŚCI WYKORZYSTANIA TRANSFORMACJI FALKOWEJ DO DETEKCJI NIEZAJĘTYCH PASM CZĘSTOTLIWOŚCI
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. 
Brief Announcement: Energy Constrained Depth First Search
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 edgeweighted 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... 
Collaborative Exploration of Trees by EnergyConstrained 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... 
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 Pcoloring). 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... 
Connections between Mutually Unbiased Bases and Quantum Random Access Codes
We present a new quantum communication complexity protocol, the promiseQuantum 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 SemiDefinite Programming techniques. 
Dynamic Ffree Coloring of Graphs
A problem of graph Ffree 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 Ffree 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... 
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 NPtrudny, 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... 
Nonmonotone 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 nonmonotone 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 kpartite 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. 
Online Search in TwoDimensional Environment
We consider the following online pursuitevasion 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 twodimensional shapes, we restrict our attention to networks that are embedded into partial grids:... 
Oxygen sensitivity of hydrogenesis’ and methanogenesis’
In the chapter, results of dark fermentation of sour cabbage in presence of oxygen with concentrations 29% 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%. 
Scheduling of unitlength 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 2chromatic then the problem can be solved in O(n^2) time. If the graph is 3chromatic, the problem becomes NPhard even if s1>s2=s3. 
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 polynomialtime 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... 
Steering is an essential feature of nonlocality in quantum theory
A physical theory is called nonlocal when observers can produce instantaneous effects over distant systems. Nonlocal 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 wellknown class of nonlocal games known as XOR games. In particular, optimal quantum strategies for XOR games are completely determined... 
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... 
Tight bounds on the complexity of semiequitable coloring of cubic and subcubic graphs
We consider the complexity of semiequitable kcoloring, k>3, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a nvertex subcubic graph G, it is NPcomplete to obtain a semiequitable kcoloring of G whose nonequitable color class is of size s if s>n/3, and it is polynomially solvable if s, n/3. 
Tradeoffs in multiparty Bellinequality violations in qubit networks
Two overlapping bipartite binary input Bell inequalities cannot be simultaneously violated as this would contradict the usual nosignalling principle. This property is known as monogamy of Bell inequality violations and generally Bell monogamy relations refer to tradeoffs between simultaneous violations of multiple inequalities. It turns out that multipartite Bell inequalities admit weaker forms of monogamies that allow for violations... 
Turán numbers for odd wheels
The Turán number ex(n,G) is the maximum number of edges in any nvertex 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... 
2017

Approximation Strategies for Generalized Binary Search in Weighted Trees
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 nonnegative weight function, and the considered objective is to minimize the total... 
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 nontrivial connected graphs with respect to the strong product. We also give an application of the abovementioned result. 
Collaborative Delivery by EnergySharing LowPower Mobile Robots
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... 
Collisionfree network exploration
Mobile agents start at different nodes of an nnode network. The agents synchronously move along the network edges in a collisionfree 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... 
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... 
Complementarity between entanglementassisted and quantum distributed random access code
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 entanglementassisted random access code (EARAC), have demonstrated equal prowess for a number of tasks. However, there do exist specific... 
Equitable coloring of corona multiproducts of graphs
We give some results regarding the equitable chromatic number for lcorona product of two graphs: G and H, where G is an equitably 3 or 4colorable graph and H is an rpartite 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
W dniach 512 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 4coloring problem is polynomially solvable and the interval incidence 5coloring problem is N Pcomplete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6coloring always exists for any subcubic graph G with ∆(G) = 3. 
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... 
NoWait & NoIdle 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. Nowait requirement enforces that the delay between operations is equal to 0. Noidle 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... 
On Computational Aspects of Greedy Partitioning of Graphs
In this paper we consider a problem of graph Pcoloring 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 Pcoloring with a least k colors is NPcomplete for an infinite... 
Realizacja zadań w grafie przez grupę mobilnych jednostek
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),... 
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).... 
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... 
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
We consider the problem of scheduling unitlength 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 NPhard,... 
Scheduling of unitlength 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 NPhard even if s1=s2=s3. If, however, delta<5 and s1>12s2 s2=s3=s4, then the problem can be solved to... 
Shared multiprocessor scheduling
We study shared multiprocessor 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... 
Szeregowanie zadań dwuprocesorowych w systemach otwartych
W pracy rozważany jest problem szeregowania zadań dwuoperacyjnych w systemie otwartym (openshop), 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ć... 
Szybkość przeszukiwania grafu
Przeszukiwanie grafu pojawiło się jako problem matematyczny ponad 40 lat temu i w najogólniejszej wersji zajmuje się odszukiwaniem jednostkiuciekiniera 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
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 prespecified. 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)... 
2016

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 NPhard for subcubic outerplanar graphs of a very simple structure (similar to cycles) and polynomially solvable for... 
Applications of semidefinite optimization in quantum information protocols
This work is concerned with the issue of applications of the semidefinite 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... 
Bounds on the cover time of parallel rotor walks
The rotorrouter 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 roundrobin fashion, according to a fixed ordering. We consider... 
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... 
Edgecoloring of 3uniform hypergraphs
We consider edgecolorings of 3uniform hypergraphs which is a natural generalization of the problem of edgecolorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NPcomplete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs. 
Eqiuitable coloring of corona products of cubic graphs is harder than ordinary coloring
A graph is equitably kcolorable 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... 
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 NPhard, we report on practical experiments with some efficient polynomialtime algorithms for approximate equitable coloring of general graphs. 
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... 
Increased Certification of Semidevice Independent Random Numbers using Many Inputs and More Postprocessing
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 multidimensional quantum systems is the increased complexity of the experimental setup. Here, we analyze a notsoobvious problem: the relation between randomness certification and computational requirements... 
Independence in uniform linear trianglefree hypergraphs
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 trianglefree 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 runiform linear trianglefree hypergraph H with r>=2. 
Lossless Compression of Binary Trees with Correlated Vertex Names
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 contextdependent. 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... 
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 precompute the sets of disjoint... 
Nonisolating 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 nonisolating bondage number of $G$, denoted by $b'(G)$, is the minimum cardinality among all sets of edges $E' \subseteq E$ such that $\delta(GE') \ge 1$ and $\gamma(GE')... 
Normalform preemption sequences for an open problem in scheduling theory
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,... 
On bipartization of cubic graphs by removal of an independent set
We study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set. 
On some open questions for Ramsey and Folkman numbers
We discuss some of our favorite open questions about Ramsey numbers and a related problem on edge Folkman numbers. For the classical twocolor 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. 
Sharp bounds for the complexity of semiequitable coloring of cubic and subcubic graphs
In this paper we consider the complexity of semiequitable kcoloring of the vertices of a cubic or subcubic graph. We show that, given nvertex subcubic graph G, a semiequitable kcoloring of G is NPhard if s >= 7n/20 and polynomially solvable if s <= 7n/21, where s is the size of maximum color class of the coloring. 
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,... 
Szeregowanie identycznych zadań na czterech procesorach jednorodnych z dwudzielnymi grafami konfliktów
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... 
2015

2outerindependent domination in graphs
We initiate the study of 2outerindependent domination in graphs. A 2outerindependent 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 2outerindependent domination number of a graph G is the minimum cardinality of a 2outerindependent dominating set of G. We show that if a graph has minimum degree at least two,... 
A bound on the number of middlestage crossbars in fcast rearrangeable Clos networks
In 2006 Chen and Hwang gave a necessary and sufficient condition under which a threestage Clos network is rearrangeable for broadcast connections. Assuming that only crossbars of the first stage have no fanout property, we give similar conditions for fcast Clos networks, where f is an arbitrary but fixed invariant of the network. Such assumptions are valid for some practical switching systems, e.g. highspeed crossconnects.... 
A TaskScheduling Approach for Efficient Sparse Symmetric MatrixVector Multiplication on a GPU
In this paper, a taskscheduling approach to efficiently calculating sparse symmetric matrixvector 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.... 
An upper bound for the double outerindependent domination number of a tree
A vertex of a graph is said to dominate itself and all of its neighbors. A double outerindependent 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 outerindependent domination number of a graph G, denoted by γ_d^{oi}(G), is the minimum cardinality of a double outerindependent dominating set of G. We prove... 
Bipartite theory of graphs: outerindependent 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$outerindependent 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$outerindependent domination number... 
Deterministic Rendezvous in Restricted Graphs
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... 
Deviceindependent quantum key distribution based on measurement inputs
We provide an analysis of a family of deviceindependent 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.... 
Distinguishing views in symmetric networks: A tight lower bound
The view of a node in a portlabeled 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 portlabeled 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. 
Distributed graph searching with a sense of direction
In this work we consider the edge searching problem for vertexweighted 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... 
Equitable and semiequitable coloring of cubic graphs and its application in batch scheduling
In the paper we consider the problems of equitable and semiequitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semiequitable coloring is NP complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unitlength jobs with cubic incompatibility graph on three uniform processors to minimize... 
Fast collaborative graph exploration
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... 
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... 
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 kpartite graphs. We also study the complexity of the... 
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... 
Minimum order of graphs with given coloring parameters
A complete kcoloring 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),... 
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 CaroWeitype and Brookstype... 
On some Zarankiewicz numbers and bipartite Ramsey Numbers for Quadrilateral
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 cyclepowers
In the paper we give some theoretical and computational results on the third strong power of cyclepowers, 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 cyclepowers. Moreover, our results establish... 
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 paireddomination numbers of a tree, AKCE International Journal of Graphs and Combinatorics 1 (2004), 6975] established the following upper bound on the total domination... 
On trees with equal 2domination and 2outerindependent domination numbers
For a graph G = (V,E), a subset D \subseteq V(G) is a 2dominating set if every vertex of V(G)\D$ has at least two neighbors in D, while it is a 2outerindependent dominating set if additionally the set V(G)\D is independent. The 2domination (2outerindependent domination, respectively) number of G, is the minimum cardinality of a 2dominating (2outerindependent dominating, respectively) set of G. We characterize all trees... 
On trees with equal domination and total outerindependent 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 outerindependent dominating set if every vertex of G has a neighbor in D, and the set V(G)D is independent. The domination (total outerindependent domination, respectively) number of G is the minimum cardinality of a dominating (total outerindependent 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. 
Rendezvous of heterogeneous mobile agents in edgeweighted 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... 
Robust amplification of SanthaVazirani sources with three devices
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.... 
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... 
The complexity of minimumlength path decompositions
We consider a bicriteria 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 ﬁxedparameter... 
The complexity of zerovisibility cops and robber
We consider the zerovisibility cops & robber game restricted to trees. We produce a characterisation of trees of copnumber k and We consider the computational complexity of the zerovisibility Cops and Robber game. We present a heavily modified version of an alreadyexisting algorithm that computes the zerovisibility copnumber of a tree in linear time and we show that the corresponding decision problem is NPcomplete on a nontrivial... 
The computational complexity of the backbone coloring problem for boundeddegree 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 boundeddegree... 
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 NPcomplete or polynomially... 
The searchlight problem for road networks
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,... 
Towards the boundary between easy and hard control problems in multicast Clos networks
In this article we study 3stage Clos networks with multicast calls in general and 2cast 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 edgecoloring. A new class of bipartite hypergraphs corresponding to Clos networks is studied. We identify some polynomially... 
Zerovisibility cops and robber and the pathwidth of a graph
We examine the zerovisibility 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 zerovisibility 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... 
2014

A survey on known values and bounds on the Shannon capacity
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. 
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. 
Bounds on the Cover Time of Parallel Rotor Walks
The rotorrouter 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... 
Bounds on the vertexedge domination number of a tree
A vertexedge 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 vertexedge domination number of a graph $G$, denoted by $\gamma_{ve}(T)$, is the minimum cardinality of a vertexedge 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 $(nls+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... 
CollisionFree Network Exploration
A set of mobile agents is placed at different nodes of a nnode network. The agents synchronously move along the network edges in a collisionfree 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...