Catálogo de publicaciones - libros

We examine the parameterized complexity of , the problem of finding a set of at most  nodes that dominate at least nodes of a graph  = (,). The classic NP-complete problem , which can be seen to be with the restriction that  = , has long been known to be W[2]-complete when parameterized in . Whereas this implies W[2]-hardness for and the parameter , we are able to prove fixed-parameter tractability for and the parameter . More precisely, we obtain a quintic problem kernel and a randomized algorithm. The algorithm is based on the divide-and-color method introduced to the community earlier this year, rather intuitive and can be derandomized using a standard framework.

Complexity of data with respect to a particular class of neural networks is studied. Data complexity is measured by the magnitude of a certain norm of either the regression function induced by a probability measure describing the data or a function interpolating a sample of input/output pairs of training data chosen with respect to this probability. The norm is tailored to a type of computational units in the network class. It is shown that for data for which this norm is “small”, convergence of infima of error functionals over networks with increasing number of hidden units to the global minima is relatively fast. Thus for such data, networks with a reasonable model complexity can achieve good performance during learning. For perceptron networks, the relationship between data complexity, data dimensionality and smoothness is investigated.

We present two novel semantics for -calculus. The first allows one to observe on which channel a synchronization is performed, while the second allows concurrent actions, provided that they do not compete for resources. We present both a reduction and a labeled semantics, and show that they induce the same behavioral equivalence. As our main result we show that bisimilarity is a congruence for the concurrent semantics. This important property fails for the standard semantics.

Terrestrial Trunked Radio (TETRA) is the most frequency-efficient standard for mobile communication and its architecture is fully scalable, from a large high-capacity system to a low-capacity system. In the TETRA standard, various attacks such as a reply attack can occur and the key-establishment scheme used in the TETRA standard requires high communication costs. In this paper, we propose an efficient group key agreement in TETRA networks that guarantees secure communication among light-weight mobile stations. That is, computation cost per mobile station is very low, only requires XOR operation on-line, and our scheme allows mobile stations and a base station to agree a group key with 1-round complexity.

The problem of finding minimum energy, edge-disjoint paths in wireless networks (MEEP) arises in the context of routing and belongs to the class of range assignment problems. A polynomial algorithm which guarantees a factor--approximation for this problem has been presented before, but its complexity status was open. In this paper we prove that MEEP is NP-hard and give new lower and upper bounds on the approximation factor of the -approximation algorithm. For MEEP on acyclic graphs we introduce an exact, polynomial algorithm which is then extended to a heuristic for arbitrary graphs.

In this paper, we continue the investigation proposed in [15] about the approximability of partition problems, but focusing here on their complexity. More precisely, we prove that the problem consisting of deciding if a graph of vertices has vertex disjoint simple paths {, ⋯ ,} such that each path has vertices is -complete, even in bipartite graphs of maximum degree 3. Note that this result also holds when each path is chordless in [()]. Then, we prove that the optimization version of these problems, denoted by and , are not in in bipartite graphs of maximum degree 3. Finally, we propose a 3/2-approximation for 3 in general graphs within ( + log) time and a 1/3 (resp., 1/2)-approximation for in general (resp., bipartite) graphs of maximum degree 3 within ((,3/2)) (resp., (log)) time, where is the inverse Ackerman’s function and  = ||,  = ||.

Similarity search is a necessary operation for applications dealing with unstructured data sources. In this paper we present a pivot-based method useful, not only to obtain a good pivot selection without specifying in advance the number of pivots, but also to obtain an insight in the complexity of the metric space. Sparse Spatial Selection (SSS) adapts itself to the dimensionality of the metric space, is dynamic, and it is suitable for secondary memory storage. In this paper we provide experimental results that confirm the advantages of the method with several metric spaces. Moreover, we explain how SSS can be easily parallelized. Finally, in this paper we conceptualize Nested Metric Spaces, and we prove that, in some applications areas, objects can be grouped in different clusters with different associated metric spaces, all of them nested into the general metric space that explains the distances among clusters.

We design a formal model of an amorphous computer suitable for theoretical investigation of its computational properties. The model consists of a finite set of nodes created by RAMs with restricted memory, which are dispersed uniformly in a given area. Within a limited radius the nodes can communicate with their neighbors via a single-channel radio. The assumptions on low-level communication abilities are among the weakest possible: the nodes work asynchronously, there is no broadcasting collision detection mechanism and no network addresses. For the underlying network we design a randomized communication protocol and analyze its efficiency. The subsequent experiments and combinatorial analysis of random networks show that the expectations under which our protocol was designed are met by the vast majority of the instances of our amorphous computer model.

The separable quadratic multi-knapsack problem () consists in maximizing a concave separable quadratic integer (non pure binary) function subject to linear capacity constraints. In this paper we develop a branch-and-bound algorithm to solve () to optimality. This method is based on the computation of a tight upper bound for () which is derived from a linearization and a surrogate relaxation. Our branch-and-bound also incorporates pre-processing procedures. The computational performance of our branch-and-bound is compared to that of three exact methods: a branch-and-bound algorithm developed by Djerdjour et al. (1988), a 0-1 linearization method originally applied to the separable quadratic knapsack problem with a single constraint that we extend to the case of constraints, a standard branch-and-bound algorithm (Cplex9.0 quadratic optimization). Our branch-and-bound clearly outperforms other methods for large instances (up to 2000 variables and constraints).

Indexing of factors is a widely used and useful technique in stringology and can be seen as a tool in solving diverse text algorithmic problems. A gapped-factor is a concatenation of a factor of length , a gap of length and another factor of length ′. The problem of indexing the gapped-factors was considered recently by [18]. In this paper, we present a new improved indexing scheme for the gapped-factors.