Search
Filters
total: 786
filtered: 683
Search results for: RANDOM BIPARTITE GRAPHS
-
The complexity of minimum-length path decompositions
PublicationWe 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 classification of the problem in terms of k and l for general graphs. Contrary to the original pathwidth problem, which is fixed-parameter...
-
Application of Doubly Connected Dominating Sets to Safe Rectangular Smart Grids
PublicationSmart grids, together with the Internet of Things, are considered to be the future of the electric energy world. This is possible through a two-way communication between nodes of the grids and computer processing. It is necessary that the communication is easy and safe, and the distance between a point of demand and supply is short, to reduce the electricity loss. All these requirements should be met at the lowest possible cost....
-
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublicationLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
NO-BROADCASTING OF NON-SIGNALLING BOXES VIA OPERATIONS WHICH TRANSFORM LOCAL BOXES INTO LOCAL ONES
PublicationWe deal with families of probability distributions satisfying non-signalling condition, called non-signalling boxes and consider a class of operations that transform local boxes into local ones (the one that admit LHV model). We prove that any operation from this class cannot broadcast a bipartite non-local box with 2 binary inputs and outputs. We consider a function called anti-Robustness which can not decrease under these operations....
-
Collective Uncertainty Entanglement Test
PublicationFor a given pure state of a composite quantum system we analyze the product of its projections onto aset of locally orthogonal separable pure states. We derive a bound for this product analogous to theentropic uncertainty relations. For bipartite systems the bound is saturated for maximally entangled statesand it allows us to construct a family of entanglement measures, we shall call collectibility. As thesequantities are experimentally...
-
Simple SIR models with Markovian control
PublicationWe consider a random dynamical system, where the deterministic dynamics are driven by a finite-state space Markov chain. We provide a comprehensive introduction to the required mathematical apparatus and then turn to a special focus on the susceptible-infected-recovered epidemiological model with random steering. Through simulations we visualize the behaviour of the system and the effect of the high-frequency limit of the driving...
-
Probabilistic Methods in Reliability Assessment of Engineering Lightweight Structures
PublicationThe paper considers the probability-based analysis of structural safety measures. Two different numerical examples of representative lightweight structures are considered – a submerged truss tower supporting an offshore platform, and an overhead power line support truss tower. On the basis of these examples, the importance of a motivated selection of analysis method and a proper choice of the number of important variables is shown....
-
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ą...
-
Dynamics of quantum entanglement
PublicationA model of discrete dynamics of entanglement of a bipartite quantum state is considered. It involves a global unitary dynamics of the system and periodic actions of local bistochastic or decaying channel. For initially pure states the decay of entanglement is accompanied by an increase of von Neumann entropy of the system. We observe and discuss revivals of entanglement due to unitary interaction of subsystems. For some mixed states...
-
All Nonclassical Correlations Can Be Activated into Distillable Entanglement
PublicationWe devise a protocol in which general nonclassical multipartite correlations produce a physically relevant effect, leading to the creation of bipartite entanglement. In particular, we show that the relative entropy of quantumness, which measures all nonclassical correlations among subsystems of a quantum system, is equivalent to and can be operationally interpreted as the minimum distillable entanglement generated between the system...
-
Entanglement and Nonlocality are Inequivalent for Any Number of Parties
PublicationUnderstanding the relation between nonlocality and entanglement is one of the fundamental problems in quantum physics. In the bipartite case, it is known that these two phenomena are inequivalent, as there exist entangled states of two parties that do not violate any Bell inequality. However, except for a single example of an entangled three-qubit state that has a local model, almost nothing is known about such a relation in multipartite...
-
Własności kwantowe przemian energetycznych zachodzących w silnikach o zapłonie samoczynnym = Quantum properties of energy transformation in diesel engines
PublicationW pracy uzasadniono, że w badaniach własności energetycznych silników spalinowych o zapłonie samoczynnym należy uwzględnić istniejącą w ich eksploatacji przypadkowość i nieprzewidywalność zdarzeń. Nawiązano do osiągnięć mechaniki kwantowej wskazując na wynikający z nich postulat, że wielkości nazywane komplementarnymi, mają istotną własność, która polega na tym, że niemożliwy jest jednoczesny i zarazem dokładny pomiar ich wartości....
-
Simple sufficient condition for subspace to be completely or genuinely entangled
PublicationWe introduce a simple sufficient criterion, which allows one to tell whether a subspace of a bipartite or multipartite Hilbert space is entangled. The main ingredient of our criterion is a bound on the minimal entanglement of a subspace in terms of entanglement of vectors spanning that subspace expressed for geometrical measures of entanglement. The criterion is applicable to both completely and genuinely entangled subspaces. We...
-
The Complexity of Zero-Visibility Cops and Robber
PublicationIn this work we deal with the computational complexity aspects of the zero-visibility Cops and Robber game. We provide an algorithm that computes the zero-visibility copnumber of a tree in linear time and show that the corresponding decision problem is NP-complete even for the class of starlike graphs.
-
Distributed graph searching with a sense of direction
PublicationIn 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...
-
A model of fuel combustion process in the marine reciprocating engine work space taking into account load and wear of crankshaft-piston assembly and the theory of semi-Markov processes
PublicationThe ar ticle analyses the operation of reciprocal internal combu stion engines, with mar ine engines u sed a s an example. The analysis takes into account types of energy conversion in the work spaces (cylinders) of these engines, loads of their crankshaft-piston assemblies, and types of fuel combustion which can take place in these spaces during engine operation. It is highlighted that the analysed time-dependent loads of marine...
-
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...
-
On minimum cost edge searching
PublicationWe consider the problem of finding edge search strategies of minimum cost. The cost of a search strategy is the sum of searchers used in the clearing steps of the search. One of the natural questions is whether it is possible to find a search strategy that minimizes both the cost and the number of searchers used to clear a given graph G. We call such a strategy ideal. We prove, by an example, that ideal search strategies do not...
-
Thermodynamical approach to quantifying quantum correlations
PublicationWe consider the amount of work which can be extracted from a heat bath using a bipartite state ρ shared by two parties. In general it is less then the amount of work extractable when one party is in possession of the entire state. We derive bounds for this “work deficit” and calculate it explicitly for a number of different cases. In particuar, for pure states the work deficit is exactly equal to the distillable entanglement of...
-
Noise Analysis of Continuous GPS Time Series of Selected EPN Stations to Investigate Variations in Stability of Monument Types
PublicationThe type of monument that a GPS antenna is placed on plays a significant role in noise estimation for each permanent GPS station. In this research 18 Polish permanent GPS stations that belong to the EPN (EUREF Permanent Network) were analyzed using Maximum Likelihood Estimation (MLE). The antennae of Polish EPN stations are placed on roofs of buildings or on concrete pillars. The analyzed data covers a period of 5 years from 2008...
-
Application of probabilistic tools to extend load test design of bridges prior to opening
PublicationLoad tests of bridges are widely performed in a large number of countries. Deterministic comparison of measurement results to the theoretical, FEM (finite element method)-based outcomes with possible further calibration is mostly applied. Sometimes, the data collected in the tests are also used to calibrate the reliability factors of bridge structures or their components. This work proposes to complement the stage of the load test...
-
On the Characteristic Graph of a Discrete Symmetric Channel
PublicationWe present some characterizations of characteristic graphs of row and/or column symmetric channels. We also give a polynomial-time algorithm that decides whether there exists a discrete symmetric channel whose characteristic graph is equal to a given input graph. In addition, we show several applications of our results.
-
Flexible Knowledge–Vision–Integration Platform for Personal Protective Equipment Detection and Classification Using Hierarchical Convolutional Neural Networks and Active Leaning
PublicationThis work is part of an effort to develop of a Knowledge-Vision Integration Platform for Hazard Control (KVIP-HC) in industrial workplaces, adaptable to a wide range of industrial environments. The paper focuses on hazards resulted from the non-use of personal protective equipment (PPE). The objective is to test the capability of the platform to adapt to different industrial environments by simulating the process of randomly selecting...
-
Analysis of Reconstituted Tripartite Complex Supports Avidity-based Recruitment of Hsp70 by Substrate Bound J-domain Protein
PublicationHsp70 are ubiquitous, versatile molecular chaperones that cyclically interact with substrate protein(s). The initial step requires synergistic interaction of a substrate and a J-domain protein (JDP) cochaperone, via its J-domain, with Hsp70 to stimulate hydrolysis of its bound ATP. This hydrolysis drives conformational changes in Hsp70 that stabilize substrate binding. However, because of the transient nature of substrate and JDP...
-
CRVG - a new model for wireless networks topology generation
PublicationThis paper presents a new model of wireless network topology generator. Its main advantage is the possibility of relatively sparse networks generation. Because no iteration is needed, the model can be used for massive generation of networks for testing. The topological properties of produced graphs place them in the class of scale free networks, resembling real ones.
-
Analysis of noise properties of the optocoupler device
PublicationIn the paper the localization of a source of Random Telegraph Signal noise (RTS noise) in optocoupler devices type CNY 17 were defined. The equivalent noise circuit in low frequency noise for these type optocouplers was proposed.
-
Examining Classifiers Applied to Static Hand Gesture Recognition in Novel Sound Mixing System
PublicationThe main objective of the chapter is to present the methodology and results of examining various classifiers (Nearest Neighbor-like algorithm with non-nested generalization (NNge), Naive Bayes, C4.5 (J48), Random Tree, Random Forests, Artificial Neural Networks (Multilayer Perceptron), Support Vector Machine (SVM) used for static gesture recognition. A problem of effective gesture recognition is outlined in the context of the system...
-
Edge-coloring of 3-uniform hypergraphs
PublicationWe consider edge-colorings of 3-uniform hypergraphs which is a natural generalization of the problem of edge-colorings of graphs. Various classes of hypergraphs are discussed and we make some initial steps to establish the border between polynomial and NP-complete cases. Unfortunately, the problem appears to be computationally difficult even for relatively simple classes of hypergraphs.
-
Scheduling of compatible jobs on parallel machines
PublicationThe dissertation discusses the problems of scheduling compatible jobs on parallel machines. Some jobs are incompatible, which is modeled as a binary relation on the set of jobs; the relation is often modeled by an incompatibility graph. We consider two models of machines. The first model, more emphasized in the thesis, is a classical model of scheduling, where each machine does one job at time. The second one is a model of p-batching...
-
Towards the boundary between easy and hard control problems in multicast Clos networks
PublicationIn 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...
-
Probabilistic sensitivity of limit states of structures : The Monte Carlo simulation
PublicationThe main issue of the paper is the probabilistic sensitivity of the limit states of structures with respect to selected input design variables. Attempt to the problem is done by the dedicated Monte Carlo simulation procedure. Basic design variables are random variables of given probability distributions, presented in the form of random numbers. Uni-parametrical increment of the dominant basic variable (basic variables) is done,...
-
Typing of Candida isolates from patients with invasive infection and concomitant colonization
PublicationWe investigated the relationship between colonizing and invasive isolates from patients with candidaemia. Molecular typing was performed using random amplification of polymorphic DNA (RAPD) and multilocus sequence typing (MLST). We found MLST to be sufficient for typing Candida isolates, and that surveillance cultures are helpful in predicting concomitant invasive isolates, but not necessarily the pathogen involved in subsequent...
-
Zastosowanie drzew decyzyjnych w prognozowaniu upadłości spółek akcyjnych
PublicationW artykule tym skupiono się na rozważaniach nad możliwością wykorzystania metody drzew decyzyjnych oraz modelu Random Forests w prognozowaniu upadłości spółek akcyjnych notowanych na Warszawskiej Giełdzie Papierów Wartościowych. W badaniach autor wykorzystał dane finansowe 107 spółek akcyjnych z lat 1998-2006. Każde z analizowanych przedsiębiorstw opisanych zostało za pomocą czternastu mierników finansowych.Celem tych badań była...
-
A space-efficient algorithm for computing the minimum cycle mean in a directed graph
PublicationAn algorithm is introduced for computing the minimum cycle mean in a strongly connected directed graph with n vertices and m arcs that requires O(n) working space. This is a considerable improvement for sparse graphs in comparison to the classical algorithms that require O(n^2) working space. The time complexity of the algorithm is still O(nm). An implementation in C++ is made publicly available at http://www.pawelpilarczyk.com/cymealg/.
-
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...
-
The complexity of zero-visibility cops and robber
PublicationWe 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...
-
Keystroke Dynamics Patterns While Writing Positive and Negative Opinions
PublicationThis paper deals with analysis of behavioural patterns in human–computer interaction. In the study, keystroke dynamics were analysed while participants were writing positive and negative opinions. A semi-experiment with 50 participants was performed. The participants were asked to recall the most negative and positive learning experiences (subject and teacher) and write an opinion about it. Keystroke dynamics were captured and...
-
Ultimate strength of stiffened plates subjected to compressive load and spatially distributed mechanical properties
PublicationThe present study deals with the ultimate strength of stiffened plates subjected to spatially distributed mechanical properties and compressive load. Normally, mean values of mechanical properties based on tensile tests are used to validate the numerical assessment with experimental results. However, mechanical properties may vary within a single specimen. To investigate the impact of that, random fields of yield stress and Young...
-
A new nethod for RTS noise of semiconductor devices identification
PublicationIn the paper, a new method, called the noise scatterin pattern method (NSP method), for random telegraph signal noise identyfication in the inherent noise of semiconductor devices is described. A block diagram of a noise measurement system based on the NSP method is presented. Examples of patterns of the NSP method are presented.
-
Parallel tabu search for graph coloring problem
PublicationTabu search is a simple, yet powerful meta-heuristic based on local search that has been often used to solve combinatorial optimization problems like the graph coloring problem. This paper presents current taxonomy of patallel tabu search algorithms and compares three parallelization techniques applied to Tabucol, a sequential TS algorithm for graph coloring. The experimental results are based on graphs available from the DIMACS...
-
Modeling of the internal combustion engine cooling system
PublicationThe article concerns computer modelling of processes in cooling systems of internal combustion engines. Modelling objectives and existing commercial programs are presented. It also describes Author’s own method of binding graphs used to describe phenomena in the cooling system of a spark ignition engine. The own model has been verified by tests on the engine dynamometer. An example of using a commercial program for experimental...
-
On the connected and weakly convex domination numbers
PublicationIn this paper we study relations between connected and weakly convex domination numbers. We show that in general the difference between these numbers can be arbitrarily large and we focus on the graphs for which a weakly convex domination number equals a connected domination number. We also study the influence of the edge removing on the weakly convex domination number, in particular we show that a weakly convex domination number...
-
A machine learning approach to classifying New York Heart Association (NYHA) heart failure
PublicationAccording to the European Society of Cardiology, globally the number of patients with heart failure nearly doubled from 33.5 million in 1990 to 64.3 million in 2017, and is further projected to increase dramatically in this decade, still remaining a leading cause of morbidity and mortality. One of the most frequently applied heart failure classification systems that physicians use is the New York Heart Association (NYHA) Functional...
-
Independence in uniform linear triangle-free hypergraphs
PublicationThe independence number a(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show a new lower bound for a(H) for an r-uniform linear triangle-free hypergraph H with r>=2.
-
Robust estimation of deformation from observation differences for free control networks
PublicationDeformation measurements have a repeatable nature. This means that deformation measurements are performed often with the same equipment, methods, geometric conditions and in a similar environment in epochs 1 and 2 (e.g., a fully automated, continuous control measurements). It is, therefore, reasonable to assume that the results of deformation measurements can be distorted by both random errors and by some non-random errors, which...
-
The semi-Markov model of the process of appearance of sea-going ship propupsion system ability and inability states in application to determining the reliablity of these systems
PublicationThe article presents possible application of the theory of semi-Markov processes in creating the eight-state model of the process of appearance of the propulsion systems ability and inability states on sea-going vessels performing transportation tasks in a relatively long operating time t (t → ∞). The model has been proved to be able to be successfully used for determining the reliability of the abovementioned systems. The probability...
-
Modelowanie szumów RTS
PublicationPrzytoczono charakterystyczne parametry szumu wybuchowego (Random Telegraph Signal, RTS). Przedstawiono algorytm programowego generatora szumów RTS. Algorytm został wyposażony w możliwość dodawania do wygenerowanych impulsów RTS szumu białego oraz szumu typu 1/f. Przedstawiono przykładowe realizacje wygenerowanych przebiegów.
-
Modelowanie szumów RTS
PublicationPrzytoczono charakterystyczne parametry szumu wybuchowego (Random Telegraph Signal, RTS). Przedstawiono algorytm programowego generatora szumów RTS. Algorytm został wyposażony w możliwość dodawania do wygenerowanych impulsów RTS szumu białego oraz szumu typu 1/f. Przedstawiono przykładowe realizacje wygenerowanych przebiegów.
-
Assessing the Effects of the Road Surface and Weather Conditions on Road Safety
PublicationWhen transport is analysed for its safe delivery the focus is mainly on assessing the safety of roads and the risk of undesired events. These include road accidents, an occurrence which is relatively rare and random. Randomness means that accidents depend on several factors which are partly deterministic (can be controlled) and partly stochastic (random and unpredictable). The set of crash contributing factors can be classified...
-
FE investigations of the effect of fluctuating local tensile strength on coupled energetic-statistical size effect in concrete beams
PublicationThe effect of fluctuating local tensile strength on a coupled energetic-statistical size effect in plain concrete beams under bending was numerically investigated. First, the influence of varying autocorrelation length of the random field describing a spatial variation of local tensile strength was studied. Next, the influence of the coefficient of variation of local tensile strength was analyzed. The numerical FE investigations...