Catálogo de publicaciones - libros

After text retrieval, the next waves in web searching and multimedia retrieval are the search for and delivery of images, music, video, and 3D scenes. Not only the perceptual and cognitive aspects, but also many of the algorithmic and performance aspects are still badly understood. One relevant issue is the design of dissimilarity measures (distance functions) that have desired properties. Another aspect is the development of algorithms that can compute or approximate these distances efficiently. Indexing data structures and search algorithms are necessary to make the search more efficient than sequential browsing through large collections. Apart from provable properties of individual algorithms, the experimental verification of the performance of a complete retrieval system is important to analyse merits and drawbacks of certain approaches, and to compare various techniques.

Sizes of quantum and deterministic finite state transducers are compared in the case when both quantum and deterministic finite state transducers exist. The difference in size may be exponential.

In the graph exploration problem, a searcher explores the whole set of nodes of an unknown graph. The searcher is not aware of the existence of an edge until he/she visits one of its endpoints. The searcher’s task is to visit all the nodes and go back to the starting node by traveling as a short tour as possible. One of the simplest strategies is the nearest neighbor algorithm (NN), which always chooses the unvisited node nearest to the searcher’s current position. The weighted NN (WNN) is an extension of NN, which chooses the next node to visit by using the weighted distance. It is known that WNN with weight 3 is 16-competitive for planar graphs. In this paper we prove that NN achieves the competitive ratio of 1.5 for cycles. In addition, we show that the analysis for the competitive ratio of NN is tight by providing an instance for which the bound of 1.5 is attained, and NN is the best for cycles among WNN with all possible weights. Furthermore, we prove that no online algorithm is better than 1.25-competitive.

In this paper we deal with making drawings of clustered hierarchical graphs nicer. Given a planar graph  = (,) with an assignment of the vertices to horizontal layers, a plane drawing of (with -monotone edges) can be specified by stating for each layer the order of the vertices lying on and the edges intersecting that layer. Given these orders and a recursive partition of the vertices into clusters, we want to draw such that (i) edges are straight-line segments, (ii) clusters lie in disjoint convex regions, (iii) no edge intersects a cluster boundary twice.

First we investigate fast algorithms that produce drawings of the above type if the clustering fulfills certain conditions. We give two fast algorithms with different preconditions. Second we give a linear programming (LP) formulation that always yields a drawing that fulfills the above three requirements—if such a drawing exists. The size of our LP formulation is linear in the size of the graph.

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph  = (,) and a spanning subgraph of (the backbone of ), a -backbone coloring for and is a proper vertex coloring →{1,2,...} of in which the colors assigned to adjacent vertices in differ by at least . The main outcome of earlier studies is that the minimum number ℓ of colors for which such colorings →{1,2,...,ℓ} exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, ℓ is at most a small additive constant (depending on ) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on ℓ than the previously known bounds.

Starting with the works by Angluin [1] and Itai and Rodeh [11], many papers have discussed the question what functions can be computed by distributed algorithms in networks where knowledge about the network topology is limited.

We investigate randomised algorithms for subset matching with spatial point sets—given two sets of -dimensional points: a data set consisting of points and a pattern consisting of points, find the largest match for a subset of the pattern in the data set. This problem is known to be 3-SUM hard and so unlikely to be solvable exactly in subquadratic time. We present an efficient bit-parallel () time algorithm and an (log) time solution based on correlation calculations using fast Fourier transforms. Both methods are shown experimentally to give answers within a few percent of the exact solution and provide a considerable practical speedup over existing deterministic algorithms.

We propose a three layer software architecture for shared resource management in mobile ad hoc networks(MANETs). At the lowest layer, the Merging Clustering Algorithm(MCA)[11] partitions the MANET into a number of balanced clusters periodically. At the second layer, the Backbone Formation Algorithm(BFA) provides a virtual ring using the clusterheads found by MCA. Finally, an example resource management protocol which is a modified and scaled version of the Ricart-Agrawala algorithm implemented using the virtual ring structure is presented with the performance results.

We consider the problem: given a (static) sequence of positive integers , such that , we wish to support the operation , which returns . Our interest is in minimising the space required for storing , where ‘minimal space’ is defined according to some compressibility criteria, while supporting sum as rapidly as possible.

There are two main compressibility criteria: (a) the space bound, bits, applies to any sequence whose elements add up to ; (b) measures, which depend on the values in , and can be lower than the succinct bound for some sequences. Appropriate data-aware measures have been studied extensively in the information retrieval (IR) community [17].

We demonstrate a close connection between the data-aware measure that is the best in practice for an important IR application and the succinct bound. We give theoretical solutions that use space close to other data-aware compressibility measures (often within () bits), and support sum in doubly-logarithmic (or better) time, and experimental evaluations of practical variants thereof.

A is a data structure that supports ‘rank/select’ on a bit-string, and is fundamental to succinct and compressed data structures. We describe a new bit-vector that is robust and efficient.

We study two aspects of a generalization of the Tower of Hanoi puzzle. In 1981, D. Wood suggested its variant, where a bigger disk may be placed a smaller one if their size difference is less than . In 1992, D. Poole suggested a natural disk-moving strategy for this problem, but only in 2005, the authors proved it be optimal in the general case. We describe the family of all optimal solutions to this problem and present a closed formula for their number, as a function of the number of disks and . Besides, we prove a tight bound for the diameter of the configuration graph of the problem suggested by Wood. Finally, we prove that the length of shortest sequence of moves, over all pairs of initial and final configurations, is the same as the above diameter, up to a constant factor.