Source author record

Eduardo Canale

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity Data Structures and Algorithms Distributed, Parallel, and Cluster Computing math.CO math.PR

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A Full Characterization of Irrelevant Components in Diameter Constrained Reliability

In classical network reliability analysis, the system under study is a network with perfect nodes but imperfect link, that fail stochastically and independently. There, the goal is to find the probability that the resulting random graph is connected, called \emph{reliability}. Although the exact reliability computation belongs to the class of $\mathcal{NP}$ -Hard problems, the literature offers three exact methods for exact reliability computation, to know, Sum of Disjoint Products (SDPs), Inclusion-Exclusion and Factorization. Inspired in delay-sensitive applications in telecommunications, Héctor Cancela and Louis Petingi defined in 2001 the diameter-constrained reliability, where terminals are required to be connected by $d$ hops or less, being $d$ a positive integer, called diameter. Factorization theory in classical network reliability is a mature area. However, an extension to the diameter-constrained context requires at least the recognition of irrelevant links, and an extension of deletion-contraction formula. In this paper, we fully characterize the determination of irrelevant links. Diameter-constrained reliability invariants are presented, which, together with the recognition of irrelevant links, represent the building-blocks for a new factorization theory. The paper is closed with a discussion of trends for future work.

preprint2014arXiv

Diameter Constrained Reliability: Computational Complexity in terms of the diameter and number of terminals

Let $G=(V,E)$ be a simple graph with $|V|=n$ nodes and $|E|=m$ links, a subset $K \subseteq V$ of \emph{terminals}, a vector $p=(p_1,\ldots,p_m) \in [0,1]^m$ and a positive integer $d$ , called \emph{diameter}. We assume nodes are perfect but links fail stochastically and independently, with probabilities $q_i=1-p_i$ . The \emph{diameter-constrained reliability} (DCR for short), is the probability that the terminals of the resulting subgraph remain connected by paths composed by $d$ links, or less. This number is denoted by $R_{K,G}^{d}(p)$ . The general DCR computation is inside the class of $\mathcal{N}\mathcal{P}$ -Hard problems, since is subsumes the complexity that a random graph is connected. In this paper, the computational complexity of DCR-subproblems is discussed in terms of the number of terminal nodes $k=|K|$ and diameter $d$ . Either when $d=1$ or when $d=2$ and $k$ is fixed, the DCR is inside the class $\mathcal{P}$ of polynomial-time problems. The DCR turns $\mathcal{N}\mathcal{P}$ -Hard when $k \geq 2$ is a fixed input parameter and $d\geq 3$ . The case where $k=n$ and $d \geq 2$ is fixed are not studied in prior literature. Here, the $\mathcal{N}\mathcal{P}$ -Hardness of this case is established.

preprint2014arXiv

Irrelevant Components and Exact Computation of the Diameter Constrained Reliability

Let $G=(V,E)$ be a simple graph with $|V|=n$ nodes and $|E|=m$ links, a subset $K \subseteq V$ of \emph{terminals}, a vector $p=(p_1,...,p_m) \in [0,1]^m$ and a positive integer $d$ , called \emph{diameter}. We assume nodes are perfect but links fail stochastically and independently, with probabilities $q_i=1-p_i$ . The \emph{diameter-constrained reliability} (DCR for short), is the probability that the terminals of the resulting subgraph remain connected by paths composed by $d$ links, or less. This number is denoted by $R_{K,G}^{d}(p)$ . The general computation of the parameter $R_{K,G}^{d}(p)$ belongs to the class of $\mathcal{N}\mathcal{P}$ -Hard problems, since is subsumes the complexity that a random graph is connected. A discussion of the computational complexity for DCR-subproblems is provided in terms of the number of terminal nodes $k=|K|$ and diameter $d$ . Either when $d=1$ or when $d=2$ and $k$ is fixed, the DCR is inside the class $\mathcal{P}$ of polynomial-time problems. The DCR turns $\mathcal{N}\mathcal{P}$ -Hard even if $k \geq 2$ and $d\geq 3$ are fixed, or in an all-terminal scenario when $d=2$ . The traditional approach is to design either exponential exact algorithms or efficient solutions for particular graph classes. The contributions of this paper are two-fold. First, a new recursive class of graphs are shown to have efficient DCR computation. Second, we define a factorization method in order to develop an exact DCR computation in general. The approach is inspired in prior works related with the determination of irrelevant links and deletion-contraction formula.

preprint2014arXiv

Robustness of Cucker-Smale flocking model

Consider a system of autonomous interacting agents moving in space, adjusting each own velocity as a weighted mean of the relative velocities of the other agents. In order to test the robustness of the model, we assume that each pair of agents, at each time step, can fail to connect with certain probability, the failure rate. This is a modification of the (deterministic) Flocking model introduced by Cucker and Smale in Emergent behavior in flocks, IEEE Trans. on Autom. Control, 2007, 52 (May) pp. 852-862. We prove that, if this random failures are independent in time and space, and have linear or sub-linear distance dependent rate of decay, the characteristic behavior of flocking exhibited by the original deterministic model, also holds true under random failures, for all failure rates.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Eduardo Canale

Research overview

Is this your work?

4 publications

A Full Characterization of Irrelevant Components in Diameter Constrained Reliability

Diameter Constrained Reliability: Computational Complexity in terms of the diameter and number of terminals

Irrelevant Components and Exact Computation of the Diameter Constrained Reliability

Robustness of Cucker-Smale flocking model

See the researcher in context

Building this map preview