This paper addresses immune sets in graphs, which are subsets of nodes that remain unaffected during the spread of influence, failure, or infection. The specific propagation model examined is the k -PULL infection rule, also referred to as bootstrap percolation . Studying immune sets offers important insights into the structural vulnerabilities and defensive capabilities of networks. In particular, we establish upper bounds for the size of minimal k -immune sets in graphs with a given maximum degree. Additionally, we focus on the k -immune number of a graph, defined as the minimum number of vertices in a k -immune set, and we derive bounds for this parameter. Lastly, we investigate the k -immune number of the Cartesian product of two graphs.

Many dissemination processes in graphs can be described as follows at a basic level. At each step of the process, some vertices of the graph are coloured blue, and the remaining are coloured white, and a well-defined infection rule acts locally on a chosen element of the graph. As an outcome of this action, perhaps one or more white vertices are forced to become blue. Zero forcing, power domination and bootstrap percolation are some examples of widely studied infection rules. This paper presents a general view of infection rules on graphs, paying particular attention to monotone rules. We state several results referring to the final stable set of blue vertices at the end of the dissemination process driven by the infection rule R, and to the combinatorial transversal relation between the families of inclusion-minimal R-forcing and R-immune sets of the graph. Our results apply to many infection rules considered in the literature, as well as to new ones introduced in this paper. Besides, for each one of these infection rules, we provide a characterization of their R-immune sets formulated in terms of neighbourhood, so without referring to the iterative dissemination process acting on the graph. In the second part of the paper, and for the particular rules treated in the first part (k-PUSH, (kb,kw)-PUSH, α-PUSH, k-PULL, α-PULL, and k-wPULL), we prove the NP-Completeness of the decision problem associated to the corresponding R-immune number of the graph.

Abstract In this article, we present a detailed study of the reach distance‐layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance‐layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance‐layer structure, we formulate explicit expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description.

Aging population is increasingly wearing a burden on healthcare institutions due to age-induced chronic illnesses. Hospitals may ran out beds and are expanding their capacities, developing Hospital at Home (HAH) units. Healthcare professionals working in HAH units visit their patients to assess their status and provide care where needed. However, most of those visits are focused on the acquisition of biometric data related to disease progression (pulse, oxygenation, temperature, etc.), using personnel that can be better used on more critical scenarios where professional medical care must be delivered. In this paper, we propose a biometric monitoring medical system for HAH units. Such device, which will continuously and remotely measure and analyze key parameters in the assessment and management of infectious disease patients so that rapid deterioration can be identified and medical personnel efficiently assigned.

Abstract We study the minimization of ADMs (Add‐Drop Multiplexers) in optical WDM bidirectional rings considering symmetric shortest path routing and all‐to‐all unitary requests. We precisely formulate the problem in terms of graph decompositions, and state a general lower bound for all the values of the grooming factorCandN, the size of the ring. We first study exhaustively the casesC= 1,C= 2, andC= 3, providing improved lower bounds, optimal constructions for several infinite families, as well as asymptotically optimal constructions and approximations. We then study the caseC> 3, focusing specifically on the caseC=k(k+ 1)/2 for somek≥ 1. We give optimal decompositions for several congruence classes ofNusing the existence of some combinatorial designs. We conclude with a comparison of the cost functions in unidirectional and bidirectional WDM rings. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 58(1), 20–35 2011

We study the following graph partitioning problem: Given two positive integers C and $\Delta$, find the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most C edges and each vertex appears in at most $M(C,\Delta)$ subgraphs. This problem is naturally motivated by traffic grooming, which is a major issue in optical networks. Namely, we introduce a new pseudodynamic model of traffic grooming in unidirectional rings, in which the aim is to design a network able to support any request graph with a given bounded degree. We show that optimizing the equipment cost under this model is essentially equivalent to determining the parameter $M(C,\Delta)$. We establish the value of $M(C,\Delta)$ for almost all values of C and $\Delta$, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between 3 and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. For these open cases, we provide upper bounds that differ from the optimal value by at most one.

We investigate whether dimensionality reduction using a latent generative model is beneficial for the task of weakly supervised scene classification. In detail we are given a set of labelled images of scenes (e.g. coast, forest, city, river, etc) and our objective is to classify a new image into one of these categories. Our approach consists of first discovering latent "topics" using probabilistic Latent Semantic Analysis (pLSA), a generative model from the statistical text literature here applied to a bag of visual words representation for each image, and subsequently training a multi-way classifier on the topic distribution vector for each image. We compare this approach to that of representing each image by a bag of visual words vector directly, and training a multi-way classifier on these vectors. To this end we introduce a novel vocabulary using dense colour SIFT descriptors, and then investigate the classification performance under changes in the size of the visual vocabulary, the number of latent topics learnt, and the type of discriminative classifier used (k-nearest neighbour or SVM). We achieve superior classification performance to recent publications that have used a bag of visual word representation, in all cases using the authors' own datasets and testing protocols. We also investigate the gain in adding spatial information. We show applications to image retrieval with relevance feedback and to scene classification in videos.

We explore the problem of classifying images by the object categories they contain in the case of a large number of object categories. To this end we combine three ingredients: (i) shape and appearance representations that support spatial pyramid matching over a region of interest. This generalizes the representation of Lazebnik et al., (2006) from an image to a region of interest (ROI), and from appearance (visual words) alone to appearance and local shape (edge distributions); (ii) automatic selection of the regions of interest in training. This provides a method of inhibiting background clutter and adding invariance to the object instance 's position; and (iii) the use of random forests (and random ferns) as a multi-way classifier. The advantage of such classifiers (over multi-way SVM for example) is the ease of training and testing. Results are reported for classification of the Caltech-101 and Caltech-256 data sets. We compare the performance of the random forest/ferns classifier with a benchmark multi-way SVM classifier. It is shown that selecting the ROI adds about 5% to the performance and, together with the other improvements, the result is about a 10% improvement over the state of the art for Caltech-256.

We present a new approach to model and classify breast parenchymal tissue. Given a mammogram, first, we will discover the distribution of the different tissue densities in an unsupervised manner, and second, we will use this tissue distribution to perform the classification. We achieve this using a classifier based on local descriptors and probabilistic Latent Semantic Analysis (pLSA), a generative model from the statistical text literature. We studied the influence of different descriptors like texture and SIFT features at the classification stage showing that textons outperform SIFT in all cases. Moreover we demonstrate that pLSA automatically extracts meaningful latent aspects generating a compact tissue representation based on their densities, useful for discriminating on mammogram classification. We show the results of tissue classification over the MIAS and DDSM datasets. We compare our method with approaches that classified these same datasets showing a better performance of our proposal.

We propose a probabilistic object classifier for outdoor scene analysis as a first step in solving the problem of scene context generation. The method begins with a top-down control, which uses the previously learned models (appearance and absolute location) to obtain an initial pixel-level classification. This information provides us the core of objects, which is used to acquire a more accurate object model. Therefore, their growing by specific active regions allows us to obtain an accurate recognition of known regions. Next, a stage of general segmentation provides the segmentation of unknown regions by a bottom-strategy. Finally, the last stage tries to perform a region fusion of known and unknown segmented objects. The result is both a segmentation of the image and a recognition of each segment as a given object class or as an unknown segmented object. Furthermore, experimental results are shown and evaluated to prove the validity of our proposal.

SONET/WDM networks using wavelength add-drop multiplexing can be constructed using certain graph decompositions used to form a grooming, consisting of unions of primitive rings. The cost of such a decomposition is the sum, over all graphs in the decomposition, of the number of vertices of nonzero degree in the graph. The existence of such decompositions with minimum cost, when every pair of sites employs no more than $\frac{1}{6}$ of the wavelength capacity, is determined with a finite number of possible exceptions. Indeed, when the number N of sites satisfies $N \equiv 1 \pmod{3}$, the determination is complete, and when $N \equiv 2 \pmod{3}$, the only value left undetermined is N = 17. When $N \equiv 0 \pmod{3}$, a finite number of values of N remain, the largest being N = 2580. The techniques developed rely heavily on tools from combinatorial design theory.

In this paper a colour texture segmentation method, which unifies region and boundary information, is proposed. The algorithm uses a coarse detection of the perceptual (colour and texture) edges of the image to adequately place and initialise a set of active regions. Colour texture of regions is modelled by the conjunction of non-parametric techniques of kernel density estimation (which allow to estimate the colour behaviour) and classical co-occurrence matrix based texture features. Therefore, region information is defined and accurate boundary information can be extracted to guide the segmentation process. Regions concurrently compete for the image pixels in order to segment the whole image taking both information sources into account. Furthermore, experimental results are shown which prove the performance of the proposed method.

Abstract Lower and upper bounds on the order of digraphs and generalized p‐cycles with a specified maximum degree and unilateral diameter are given for generic values of the parameters. Infinite families of digraphs attaining the bounds asymptotically or even exactly are presented. In particular, optimal results are proved for bipartite digraphs (p = 2) and digraphs with unilateral diameter 3. © 2003 Wiley Periodicals, Inc.

One of the major problems in machine vision is the segmentation of images of natural scenes. This paper presents a new proposal for the image segmentation problem which has been based on the integration of edge and region information. The main contours of the scene are detected and used to guide the posterior region growing process. The algorithm places a number of seeds at both sides of a contour allowing stating a set of concurrent growing processes. A previous analysis of the seeds permits to adjust the homogeneity criterion to the regions's characteristics. A new homogeneity criterion based on clustering analysis and convex hull construction is proposed.

Image segmentation of natural scenes constitutes a major problem in machine vision. This paper presents a new proposal for the image segmentation problem which has been based on the integration of edge and region information. This approach begins by detecting the main contours of the scene which are later used to guide a concurrent set of growing processes. A previous analysis of the seed pixels permits adjustment of the homogeneity criterion to the region's characteristics during the growing process. Since the high variability of regions representing outdoor scenes makes the classical homogeneity criteria useless, a new homogeneity criterion based on clustering analysis and convex hull construction is proposed. Experimental results have proven the reliability of the proposed approach.

This paper presents an interface for the interaction between a human and an adapted kitchen where different elements, including a robot, have to be controlled. After the global structure of the interface is described a more detailed explanation is presented on the way the interface offers the user an easy and friendly way to select the desired objects and to provide their position to the robot for their manipulation.

Large digraphs of a specified maximum degree and unilateral diameter are given for small values of these parameters. The constructions are based on different techniques such as voltage digraphs, digraph products, join of cycles, and vertex duplication. Finally, a table with the results is given. © 2000 John Wiley & Sons, Inc.

The purpose of this paper is to find fault-tolerant fixed routings in some families of digraphs that have been widely considered into the design of interconnection networks. A routing $\rho$ in a digraph G assigns to each pair of vertices a fixed path (called a route) between them. For a given set of faulty vertices and/or arcs, the vertices of the surviving route digraph are the nonfaulty vertices and there is an arc between two vertices if and only if there are no faults on the route between them. The diameter of the surviving route digraph measures the fault tolerance of the routing. In this work, sufficient conditions are found for a digraph to have a routing such that for any set of faults with a bounded number of elements the diameter of the surviving route digraph is at most 3. These results are applied to prove the existence of routings with this property in the generalized de Bruijn and Kautz digraphs, the bipartite digraphs BD(d,n), and general iterated line digraphs.