Search

Highly dynamic networks rarely offer end-to-end connectivity at a given time. Yet, connectivity in these networks can be established over time and space, based on temporal analogues of multi-hop paths (also called journeys). Attempting to optimize the selection of the journeys in these networks naturally leads to the study of three cases: shortest (minimum hop), fastest (minimum duration), and foremost (earliest arrival) journeys. Efficient centralized algorithms exists to compute all cases, when the full knowledge of the network evolution is given. In this paper, we study the distributed counterparts of these problems, i.e. shortest, fastest, and foremost broadcast with termination detection (TDB), with minimal knowledge on the topology. We show that the feasibility of each of these problems requires distinct features on the evolution, through identifying three classes of dynamic graphs wherein the problems become gradually feasible: graphs in which the re-appearance of edges is recurrent (class ), bounded-recurrent (), or periodic (), together with specific knowledge that are respectively n (the number of nodes), Δ (a bound on the recurrence time), and p (the period). In these classes it is not required that all pairs of nodes get in contact - only that the overall footprint of the graph is connected over time. Our results, together with the strict inclusion between , , and , implies a feasibility order among the three variants of the problem, i.e. TDB[ foremost] requires weaker assumptions on the topology dynamics than TDB[ shortest], which itself requires less than TDB[ fastest]. Reversely, these differences in feasibility imply that the computational powers of , , and also form a strict hierarchy. [ABSTRACT FROM AUTHOR]

Min-degree constrained minimum spanning tree (md-MST) problem is an NP-hard combinatorial optimization problem seeking for the minimum weight spanning tree in which the vertices are either of degree one (leaf) or at least degree d > 2. md-MST problem is new to the literature and very few studies have been conducted on this problem in deterministic graph. md-MST problem has several appealing real-world applications. Though in realistic applications the graph conditions and parameters are stochastic and vary with time, to the best of our knowledge no work has been done on solving md-MST problem in stochastic graph. This paper proposes a decentralized learning automata-based algorithm for finding a near optimal solution to the md-MST problem in stochastic graph. In this work, it is assumed that the weight associated with the graph edge is random variable with a priori unknown probability distribution. This assumption makes the md-MST problem incredibly harder to solve. The proposed algorithm exploits an intelligent sampling technique avoiding the unnecessary samples by focusing on the edges of the min-degree spanning tree with the minimum expected weight. On the basis of the Martingale theorem, the convergence of the proposed algorithm to the optimal solution is theoretically proven. Extensive simulation experiments are performed on the stochastic graph instances to show the performance of the proposed algorithm. The obtained results are compared with those of the standard sampling method in terms of the sampling rate and solution optimality. Simulation experiments show that the proposed method outperforms the standard sampling method. [ABSTRACT FROM AUTHOR]

In this paper, we present techniques and algorithms for processing an offline sequence of update and query operations and for related problems. The update can be either all insertions or all deletions. The types of query include min-gap, max-gap, predecessor, and successor. Most problems we consider are solved optimally in linear time by our algorithms, which are based on new geometric modeling and interesting techniques. We also discuss some applications to which our algorithms and techniques can be applied to yield efficient solutions. These applications include an offline horizontal ray shooting problem and a shortest arc covering problem on a circle. [ABSTRACT FROM AUTHOR]

This paper explores the phase transitions of the EXPSPACE-complete problems, which mainly focus on the conformant planning problems. The research presents two conformant planning algorithms-CONFORMANT PLAN-NONEXISTENCE algorithm and CONFORMANT PLAN-EXISTENCE algorithm. By analyzing the features of the two algorithms, the phase transition area of the conformant planning problems is obtained. If the number of the operators isn't greater than θub, the CONFORMANT PLAN-NONEXISTENCE algorithm can prove that nearly all the conformant planning instances have no solution. If the number of the operators isn't lower than θlb, the CONFORMANT PLAN-EXISTENCE algorithm can prove that nearly all the conformant planning instances have solutions. The results of the experiments show that there exist phase transitions from a region where almost all the conformant planning instances have no solution to a region where almost all the conformant planning instances have solutions. [ABSTRACT FROM AUTHOR]

DNA microarray technology has proven to be an invaluable tool for molecular biologists. Microarrays are used extensively in SNP detection, genomic hybridization, alternative splicing and gene expression profiling. However the manufacturers of the microarrays are often stuck with the problem of minimizing the effects of unwanted illumination (border length minimization (BLM)) which is a hard combinatorial problem. In this paper we prove that the BLM problem on a rectangular grid is NP-hard - this however does not mean the BLM problem on a square grid is NP-hard. We also give the first integer linear programming (ILP) formulation to solve BLM problem optimally. Experimental results indicate that our ILP method produces superior results (both in runtime and cost) compared to the current state of the art algorithms to solve the BLM problem optimally. [ABSTRACT FROM AUTHOR]