Search
Filters
total: 487
filtered: 379
Search results for: equitable graph coloring
-
Study of the Flow Dynamics of Surface Water Masses in the Area of the Coastal Gulf of Gdansk
PublicationThe paper describes two methods of predicting the movement of small objects with surface water masses. One of the methods uses graph theory to describe the motion of water masses in port docks. The results of this study were compared to a simulation using the hydrodynamic numerical model M3D. The results obtained in a virtual environment were related to the experiments in the real world. In the coastal area of the Gulf of Gdansk,...
-
On-line Search in Two-Dimensional Environment
PublicationWe consider the following on-line pursuit-evasion problem. A team of mobile agents called searchers starts at an arbitrary node of an unknown network. Their goal is to execute a search strategy that guarantees capturing a fast and invisible intruder regardless of its movements using as few searchers as possible. We require that the strategy is connected and monotone, that is, at each point of the execution the part of the graph...
-
Certified domination
PublicationImagine that we are given a set D of officials and a set W of civils. For each civil x ∈ W, there must be an official v ∈ D that can serve x, and whenever any such v is serving x, there must also be another civil w ∈ W that observes v, that is, w may act as a kind of witness, to avoid any abuse from v. What is the minimum number of officials to guarantee such a service, assuming a given social network? In this paper, we introduce...
-
A city is not a tree: a multi-city study on street network and urban life
PublicationChristopher Alexander, a British-American scholar, differentiated an old (natural) city from a new (planned) one by structure. The former resembles a “semilattice”, or a complex system encompassing many interconnected sub-systems. The latter is shaped in a graph-theoretical “tree”, which lacks the structural complexity as its sub-systems are compartmentalized into a single hierarchy. This structural distinction explains why, or...
-
On trees with equal domination and total outer-independent domination numbers
PublicationFor 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...
-
On trees with equal 2-domination and 2-outer-independent domination numbers
PublicationFor 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...
-
The Snow Team Problem
PublicationWe 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)...
-
Scheduling of unit-length jobs with bipartite incompatibility graphs on four uniform machines
PublicationThe 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...
-
Asynchronous Networked Estimation System for Continuous Time Stochastic Processes
PublicationIn this paper we examine an asynchronous networked estimation system for state estimation of continuous time stochastic processes. Such a system is comprised of several estimation nodes connected using a possibly incomplete communication graph. Each of the nodes uses a Kalman filter algorithm and data from a local sensor to compute local state estimates of the process under observation. It also performs data fusion of local estimates...
-
Characterizing the Performance of <span class="sc">xor</span> Games and the Shannon Capacity of Graphs
PublicationIn this Letter we give a set of necessary and sufficient conditions such that quantum players of a two-party xor game cannot perform any better than classical players. With any such game, we associate a graph and examine its zero-error communication capacity. This allows us to specify a broad new class of graphs for which the Shannon capacity can be calculated. The conditions also enable the parametrization of new families of games...
-
Ontology-Driven Rule-Based Model for an Extension of Information Technology Infrastructure Library Processes
PublicationThe aim of this study is to present the stages for building a development model to create information technology (IT) systems for IT service providers. In order to ensure the consistency of the model, a novel solution is proposed where the stages of the model's construction are controlled using ontologies dedicated to the ITIL standard. In this article, a description of models used to assess the provider organization, with particular...
-
Błędy w przedstawianiu wyników pomiarów i wartości wielkości fizycznych popełniane w pracach studenckich
PublicationArtykuł powstał na bazie doświadczeń zdobytych podczas pracy dydaktycznej autora jako wykładowcy i nauczyciela akademickiego prowadzącego zajęcia w Laboratorium Podstaw Metrologii. Przytoczono przykłady nieprawidłowości w przedsta-wianiu wyników pomiarów i wartości wielkości fizycznych pochodzące z prac pisemnych studentów i skonfrontowano je z zaleceniami Międzynarodowego Układu Jednostek Miar (SI), oraz polskimi aktami prawnymi.
-
Distributed state estimation using a network of asynchronous processing nodes
PublicationWe consider the problem of distributed state estimation of continuous-time stochastic processes using a~network of processing nodes. Each node performs measurement and estimation using the Kalman filtering technique, communicates its results to other nodes in the network, and utilizes similar results from the other nodes in its own computations. We assume that the connection graph of the network is not complete, i.e. not all nodes...
-
Global edge alliances in graphs
PublicationIn the paper we introduce and study a new problem of finding a minimum global edge alliance in a graph which is related to the global defensive alliance (Haynes et al., 2013; Hedetniemi, 2004) and the global defensive set (Lewoń et al., 2016). We proved the NP-completeness of the global edge alliance problem for subcubic graphs and we constructed polynomial time algorithms for trees. We found the exact values of the size of the...
-
The application of nonlinear curvature sections in the turnout diverging track
PublicationThe paper presents the analytical method of modelling the diverging track of railway turnout with nonlinear curvature sections. These sections were used for smoothing the graph of curvature in the extreme areas of turnout. The problem of the curvature distribution was identified with the use of differential equations. The resulting solutions are of universal nature for example the ability of assuming any values of curvature at...
-
Distributed state estimation using a network of asynchronous processing nodes
PublicationWe consider the problem of distributed state estimation of continuous-time stochastic processes using a~network of processing nodes. Each node performs measurement and estimation using the Kalman filtering technique, communicates its results to other nodes in the network, and utilizes similar results from the other nodes in its own computations. We assume that the connection graph of the network is not complete, i.e. not all nodes...
-
Bipartite theory of graphs: outer-independent domination
PublicationLet $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...
-
Parallel Computations of Text Similarities for Categorization Task
PublicationIn this chapter we describe the approach to parallel implementation of similarities in high dimensional spaces. The similarities computation have been used for textual data categorization. A test datasets we create from Wikipedia articles that with their hyper references formed a graph used in our experiments. The similarities based on Euclidean distance and Cosine measure have been used to process the data using k-means algorithm....
-
Knowledge-based functional safety management using ProSIL software
PublicationIn the article the ProSIL software for computer aided functional safety management is presented. The software consists of three modules for the determination of the required SIL level (ProSILen) and verification of the SIL level (ProSILver). In the ProSIL the calibrated knowledge-based risk graph method for determining the required safety integrity level (SIL) of the safety functions identified in hazard analysis is implemented....
-
Big Data i 5V – nowe wyzwania w świecie danych (Big Data and 5V – New Challenges in the World of Data)
PublicationRodzaje danych, składające się na zbiory typu Big Data, to m.in. dane generowane przez użytkowników portali internetowych, dane opisujące transakcje dokonywane poprzez Internet, dane naukowe (biologiczne, astronomiczne, pomiary fizyczne itp.), dane generowane przez roboty w wyniku automatycznego przeszukiwania przez nie Internetu (Web mining, Web crawling), dane grafowe obrazujące powiązania pomiędzy stronami WWW itd. Zazwyczaj,...
-
Hat problem on the cycle C4
PublicationThe topic of our paper is the hat problem. In that problem, each of n people is randomly tted with a blue or red hat. Then everybody can try to guess simultanously his own hat color looking at the hat colors of the other people. The team wins if at least one person guesses his hat color correctly and no one guesses his hat color wrong, otherwise the team loses. The aim is to maximize the probability of win. In this version every...
-
The hat problem on a union of disjoint graphs
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...
-
Mitigation of Fake Data Content Poisoning Attacks in NDN via Blockchain
PublicationAbstract—Information-centric networks struggle with content poisoning attacks (CPAs), especially their stronger form called Fake Data CPA, in which an intruder publisher uploads content signed with stolen credentials. Following an existing graphinfection based approach leveraging the constrained time when stolen credentials are useful, we design a blockchain-based mitigation scheme for Named Data Networking architectures. We postulate...
-
An O ( n log n ) algorithm for finding edge span of cacti
PublicationLet 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...
-
Global defensive secure structures
PublicationLet S ⊂ V (G) for a given simple non-empty graph G. We define for any nonempty subset X of S the predicate SECG,S(X) = true iff |NG[X]∩S| ≥ |NG[X]\S|. Let H be a non-empty family of graphs such that for each vertex v ∈ V (G) there is a subgraph H of G containing v and isomorphic to a member of H. We introduce the concept of H-alliance extending the concept of global defensive secure structures. By an H-alliance in a graph G we...
-
On the partition dimension of trees
PublicationGiven an ordered partition Π={P1,P2,…,Pt} of the vertex set V of a connected graph G=(V,E), the partition representation of a vertex v∈V with respect to the partition Π is the vector r(v|Π)=(d(v,P1),d(v,P2),…,d(v,Pt)), where d(v,Pi) represents the distance between the vertex vv and the set Pi. A partition Π of V is a resolving partition of G if different vertices of G have different partition representations, i.e., for every...
-
Graphs with equal domination and certified domination numbers
PublicationA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
Polynomial Algorithm for Minimal (1,2)-Dominating Set in Networks
PublicationDominating sets find application in a variety of networks. A subset of nodes D is a (1,2)-dominating set in a graph G=(V,E) if every node not in D is adjacent to a node in D and is also at most a distance of 2 to another node from D. In networks, (1,2)-dominating sets have a higher fault tolerance and provide a higher reliability of services in case of failure. However, finding such the smallest set is NP-hard. In this paper, we...
-
Clearing directed subgraphs by mobile agents
PublicationWe study several problems of clearing subgraphs by mobile agents in digraphs. The agents can move only along directed walks of a digraph and, depending on the variant, their initial positions may be pre-specified. In general, for a given subset S of vertices of a digraph D and a positive integer k, the objective is to determine whether there is a subgraph H=(V,A) of D such that (a) S is a subset of V, (b) H is the union of k directed...
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Comparing Phylogenetic Trees by Matching Nodes Using the Transfer Distance Between Partitions
PublicationAbility 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...
-
Research into the Movements of Surface Water Masses in the Basins Adjacent to the Port
PublicationThis paper presents the results of the practical and simulation research into determining the routes of movement of small objects moving together with surface water masses in basins adjacent to the port. The results of this research were referenced against the modelling of routes of small objects in port channel basins. The results of practical research concerning the movement of small objects in basins adjacent to the port were...
-
On a matching distance between rooted phylogenetic trees
PublicationThe Robinson–Foulds (RF) distance is the most popular method of evaluating the dissimilarity between phylogenetic trees. In this paper, we define and explore in detail properties of the Matching Cluster (MC) distance, which can be regarded as a refinement of the RF metric for rooted trees. Similarly to RF, MC operates on clusters of compared trees, but the distance evaluation is more complex. Using the graph theoretic approach...
-
Extending Service Selection Algorithms with Interoperability Analysis
PublicationApplication development by integration of existing, atomic services reduces development cost and time by extensive reuse of service components. In Service Oriented Architecture, there exist alternative versions of services supplying the same functionality but differing in Quality of Service (QoS) attributes, which enables developers to select services with optimal QoS. Existing algorithms of service selection focus on the formal...
-
Eventual Convergence of the Reputation-Based Algorithm in IoT Sensor Networks
PublicationUncertainty in dense heterogeneous IoT sensor networks can be decreased by applying reputation-inspired algorithms, such as the EWMA (Exponentially Weighted Moving Average) algorithm, which is widely used in social networks. Despite its popularity, the eventual convergence of this algorithm for the purpose of IoT networks has not been widely studied, and results of simulations are often taken in lieu of the more rigorous proof....
-
Applying case studies to teaching architectural investment
PublicationCase studies enable students to encounter practical issues during their education. Experiments conducted in class employing this method often feature simplified models of real-world situations. However, they still enable students to encounter actual problems, to which theoretical knowledge is applied. In architectural education, students carrying out semester projects usually rely on data provided by the teacher, without wondering...
-
Concept of Multifactor Method and Non-Functional Requirements Solution to Increase Resilience through Functional Safety with Cybersecurity Analysis
PublicationIn the process of designing safety systems, an integrated approach in safety and cybersecurity analysis is necessary. The paper describes a new technique of increasing resilience through integrated analysis of functional safety and cybersecurity. It is a modeling methodology based on the combination of the multifactor method utilizing modified risk graphs, used previously for Safety Integrity Level (SIL) assessment, and the Non-Functional...
-
Dobór optymalnej liczby jednostek funcjonalnych dla realizacji syntezy wysokiego poziomu układów cyfrowych
PublicationW pracy przedstawiono algorytm MNP (ang. minimization the number of procesing elements) wyznaczający liczbę jednostek funkcjonalnych niezbędnych do syntezy wysokiego poziomu zadania opisanego grafem przepływu danych (DFG - ang. data flow graph). Liczba jednostek funkcjonalnych wyznaczana przez prezentowany algorytm jest optymalna zarówno z punktu widzenia kosztów wykonania układu, jak i szybkości jego działania. Rozwiązanie tego...
-
Żółte barwniki organiczne w XIX-wiecznych farbach Jana Matejki - identyfikacja substancji barwiących, nośników, oraz wypełniaczy
PublicationNaturalne barwniki organiczne można znaleźć w wielu obiektach dziedzictwa kulturowego. Identyfikacja substancji barwiących obecnych w farbach historycznych dostarcza istotnych informacji dla wielu specjalistów zaangażowanych w naukę o sztuce. Identyfikacja składu farb pozwala na zastosowanie odpowiednich procedur dotyczących renowacji i konserwacji historycznych dzieł sztuki. Informacje te pozwalają na ich renowację zgodnie z decyzjami...
-
Synchronous black hole search in directed graphs
PublicationThe paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...
-
Modele i algorytmy dla grafowych struktur defensywnych
PublicationW niniejszej pracy przeprowadzono analizę złożoności istnienia struktur defensywnych oraz równowag strategicznych w grafach. W przypadku struktur defensywnych badano modele koalicji defensywnych, zbiorów defensywnych i koalicji krawędziowych – każdy z nich w wersji globalnej, tj. z wymogiem dominacji całego grafu. W przypadku modeli równowagi strategicznej badano równowagę strategiczną koalicji defensywnych, równowagę strategiczną...
-
A model, design, and implementation of an efficient multithreaded workflow execution engine with data streaming, caching, and storage constraints
PublicationThe paper proposes a model, design, and implementation of an efficient multithreaded engine for execution of distributed service-based workflows with data streaming defined on a per task basis. The implementation takes into account capacity constraints of the servers on which services are installed and the workflow data footprint if needed. Furthermore, it also considers storage space of the workflow execution engine and its cost....
-
Total Domination Versus Domination in Cubic Graphs
PublicationA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...
-
Wpływ struktur wsparcia na efektywność nauczania języka pisanego w środowisku e-learningowym
PublicationThe process of knowledge and language skills development during an online course can be very effective if student engagement in learning is achieved. This can be attained by introducing general and specific support mechanisms prior to the commencement of the course and during it. The former relates to the technological aspect, that is to familiarizing students with the functionalities of the virtual learning environment they will...
-
Mitigating Time-Constrained Stolen-Credentials Content Poisoning in an NDN Setting
PublicationNDN is a content-centric networking architecture using globally addressable information objects, created by publishers and cached by network nodes to be later accessed by subscribers. Content poisoning attacks consist in the substi-tution by an intruder publisher of bogus objects for genuine ones created by an honest publisher. With valid credentials stolen from an honest publisher, such attacks seem unstoppa-ble unless object...
-
Scanning networks with cactus topology
PublicationThe family of Pursuit and Evasion problems is widelystudied because of its numerous practical applications,ranging from communication protocols to cybernetic andphysical security. Calculating the search number of a graphis one of most commonly analyzed members of this problemfamily. The search number is the smallest number of mobileagents required to capture an invisible and arbitrarily fastfugitive, for instance piece of malicious...
-
Interoperability Constraints in Service Selection Algorithms
PublicationIn Service Oriented Architecture, composite applications are developed by integration of existing, atomic services that may be available in alternative versions realizing the same functionality but having different Quality of Service (QoS) attributes. The development process requires effective service selection algorithms that balance profits and constraints of QoS attributes. Additionally, services operate in a heterogeneous environment,...
-
A Model of Thermal Energy Storage According to the Convention of Bond Graphs (BG) and State Equations (SE)
PublicationThe main advantage of the use of the Bond Graphs method and State Equations for modeling energy systems with a complex structure (marine power plants, hybrid vehicles, etc.) is the ability to model the system components of different physical nature using identical theoretical basis. The paper presents a method of modeling thermal energy storage, which is in line with basic BG theory. Critical comments have been put forward concerning...
-
Comparison of selected algorithms for scheduling workflow applications with dynamically changing service availability
PublicationThis paper compares the quality and execution times of several algorithms for scheduling service based workflow applications with changeable service availability and parameters. A workflow is defined as an acyclic directed graph with nodes corresponding to tasks and edges to dependencies between tasks. For each task, one out of several available services needs to be chosen and scheduled to minimize the workflow execution time and...
-
Three levels of fail-safe mode in MPI I/O NVRAM distributed cache
PublicationThe paper presents architecture and design of three versions for fail-safe data storage in a distributed cache using NVRAM in cluster nodes. In the first one, cache consistency is assured through additional buffering write requests. The second one is based on additional write log managers running on different nodes. The third one benefits from synchronization with a Parallel File System (PFS) for saving data into a new file which...