A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.     

An efficient algorithm for positive realizations

We observe that successive applications of known results from the theory of positive systems lead to an efficient general algorithm for positive realizations of transfer functions. We give two examples to illustrate the algorithm, one of which complements an earlier result of [L. Benvenuti, L. Farina, An example of how positivity may force realizations of ‘large’ dimensions, Systems Control Lett. 36 (1999) 261–266]. Finally, we improve a lower-bound of [B. Nagy, M. Matolcsi, A lower-bound on the dimension of positive realizations, IEEE Trans. Circuits Syst. I 50 (2003) 782–784] to indicate that the algorithm is indeed efficient in general.     

On Word Equations in One Variable

For a word equation E of length n in one variable x occurring # _x times in E a resolution algorithm of O(n+# _x log n) time complexity is presented here. This is the best result known and for the equations that feature #_x < \fracnlogn\#_{x}<\frac{n}{\log n} it yields time complexity of O(n) which is optimal. Additionally it is proven here that the set of solutions of any one-variable word equation is either of the form F or of the form F∪(uv)⁺ u where F is a set of O(log n) words and u, v are some words such that uv is a primitive word.     

Interpretable segmentation of medical free-text records based on word embeddings

Journal of Intelligent Information Systems - Medical free-text records store a lot of useful information that can be exploited in developing computer-supported medicine. However, extracting the...     

MapReduce approach to relational influence propagation in complex networks

The relational label propagation problem for large data sets using MapReduce programming model was considered in the paper. The method we propose estimates class probability in relational domain in the networks. The method was examined on large real telecommunication data set. The results indicated that it could be used successfully to classify networks’ nodes and, thanks to that, new offerings or tariffs might be proposed to customers who belong to other providers. Moreover, basic properties of relational label propagation were examined and reported.     

Using Convex Sets for Exploratory Data Analysis and Visualization

In this paper a new, abstract method for analysis and visualization of multidimensional data sets in pattern recognition problems is introduced. It can be used to determine the properties of an unknown, complex data set and to assist in finding the most appropriate recognition algorithm. Additionally, it can be employed to design layers of a feedforward artificial neural network or to visualize the higher-dimensional problems in 2-D and 3-D without losing relevant data set information. The method is derived from the convex set theory and works by considering convex subsets within the data and analyzing their respective positions in the original dimension. Its ability to describe certain set features that cannot be explicitly projected into lower dimensions sets it apart from many other visualization techniques. Two classical multidimensional problems are analyzed and the results show the usefulness of the presented method and underline its strengths and weaknesses.     

Hydrophilic polycarbonate chips for generation of oil-in-water (O/W) and water-in-oil-in-water (W/O/W) emulsions

Modification of the surfaces of polycarbonate (PC) with the use of a solution of tin (II) chloride renders them hydrophilic. The surface draping is stable against exposure to water and to alcohols. Exposure to alkanes reduces but does not diminish the effect. The method is compatible—in using the same solvent and temperature—with the hydrophobic modification of PC Jankowski et al. ( Lab Chip 11:748–752, 2011). The combination of these methods makes it possible to generate single and multiple monodisperse emulsions with the use of flow-focusing junctions in systems made in PC—material that is suitable for fabrication of multilayer, high throughput microfluidic devices.     

Methods for constraint violation suppression in the numerical simulation of constrained multibody systems – A comparative study

Multibody systems are frequently modeled as constrained systems, and the arising governing equations incorporate the closing constraint equations at the acceleration level. One consequence of accumulation of integration truncation errors is the phenomenon of violation of the lower-order constraint equations by the numerical solutions to the governing equations. The constraint drift usually tends to increase in time and may spoil reliability of the simulation results. In this paper a comparative study of three methods for constraint violation suppression is presented: the popular Baumgarte’s constraint violation stabilization method, a projective scheme for constraint violation elimination, and a novel scheme patterned after that proposed recently by Braun and Goldfarb [D.J. Braun, M. Goldfarb, Eliminating constraint drift in the numerical simulation of constrained dynamical systems, Comput. Meth. Appl. Mech. Engrg., 198 (2009) 3151–3160]. The methods are confronted with respect to simplicity in applications, numerical effectiveness and influence on accuracy of the constraint-consistent motion.     

Risk assessment for a video surveillance system based on Fuzzy Cognitive Maps

For various IT systems security is considered a key quality factor. In particular, it might be crucial for video surveillance systems, as their goal is to provide continuous protection of critical infrastructure and other facilities. Risk assessment is an important activity in security management; it aims at identifying assets, threats and vulnerabilities, analysis of implemented countermeasures and their effectiveness in mitigating risks. This paper discusses an application of a new risk assessment method, in which risk calculation is based on Fuzzy Cognitive Maps (FCMs) to a complex automated video surveillance system. FCMs are used to capture dependencies between assets and FCM based reasoning is applied to aggregate risks assigned to lower-level assets (e.g. cameras, hardware, software modules, communications, people) to such high level assets as services, maintained data and processes. Lessons learned indicate, that the proposed method is an efficient and low-cost approach, giving instantaneous feedback and enabling reasoning on effectiveness of security system.     

Path‐space Motion Estimation and Decomposition for Robust Animation Filtering

Renderings of animation sequences with physics‐based Monte Carlo light transport simulations are exceedingly costly to generate frame‐by‐frame, yet much of this computation is highly redundant due to the strong coherence in space, time and among samples. A promising approach pursued in prior work entails subsampling the sequence in space, time, and number of samples, followed by image‐based spatio‐temporal upsampling and denoising. These methods can provide significant performance gains, though major issues remain: firstly, in a multiple scattering simulation, the final pixel color is the composite of many different light transport phenomena, and this conflicting information causes artifacts in image‐based methods. Secondly, motion vectors are needed to establish correspondence between the pixels in different frames, but it is unclear how to obtain them for most kinds of light paths (e.g. an object seen through a curved glass panel). To reduce these ambiguities, we propose a general decomposition framework, where the final pixel color is separated into components corresponding to disjoint subsets of the space of light paths. Each component is accompanied by motion vectors and other auxiliary features such as reflectance and surface normals. The motion vectors of specular paths are computed using a temporal extension of manifold exploration and the remaining components use a specialized variant of optical flow. Our experiments show that this decomposition leads to significant improvements in three image‐based applications: denoising, spatial upsampling, and temporal interpolation.