Catálogo de publicaciones - libros

With recent advances in terrain-mapping technologies such as Laser altimetry (LIDAR) and ground based laser scanning, millions of georeferenced points can be acquired within short periods of time. However, while acquiring and georeferencing the data has become extremely efficient, transforming the resulting massive amounts of heterogeneous data to useful information for different types of users and applications is lagging behind, in large part because of the scarcity of robust, efficient algorithms for terrain modeling and analysis that can handle massive data sets acquired by different technologies and that can rapidly detect and predict changes in the model as the new data is acquired.

We are concerned with coloring graphs that embed in a fixed surface. This restriction often makes coloring problems tractable, and the purpose of this abstract is to describe a new result along these lines.

By a we mean a compact 2-dimensional manifold with empty boundary. The classification theorem of surfaces states that every surface is homeomorphic to either the surface obtained from the sphere by adding handles (“the orientable surface of genus ”), or to the surface obtained from the sphere by adding “cross-caps” (“the non-orientable surface of cross-cap number ”). We refer to [8] for background information on surfaces and graphs embedded in them.

Thomassen initiated a systematic study of coloring graphs on surfaces by formulating two related questions. The first one asks for the complexity status of the following decision problem for fixed integers and and a fixed surface .

We examine the problem of integer representation in near minimal number of bits so that increment and decrement (and indeed addition and subtraction) can be performed using few bit inspections and fewer bit changes. In particular, we prove a new lower bound of for the increment and decrement operation, where is the minimum number of bits required to represent the number. The model of computation we considered is the bit probe model, where the complexity measure counts only the bitwise accesses to the data structure. We present several efficient data structures to represent integer that use a logarithmic number of bit inspections and a constant number of bit changes per operation.

It is known that, given an edge-weighted graph, a maximum adjacency ordering (MA ordering) of vertices can find a special pair of vertices, called a , and that a minimum cut in a graph can be found by repeatedly contracting a pendent pair, yielding one of the fastest and simplest minimum cut algorithms. In this paper, we provide another ordering of vertices, called a minimum degree ordering (MD ordering) as a new fundamental tool to analyze the structure of graphs. We prove that an MD ordering finds a different type of special pair of vertices, called a , which actually can be obtained as the last two vertices after repeatedly removing a vertex with the minimum degree. By contracting flat pairs, we can find not only a minimum cut but also all extreme subsets of a given graph. These results can be extended to the problem of finding extreme subsets in symmetric submodular set functions.

Let  = (,) be a simple undirected graph with a set of vertices and a set of edges. Each vertex  ∈  has a demand () ∈ , and a cost () ∈ , where and denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph asks to find a set of vertices minimizing ∑ () such that there are at least () pairwise vertex-disjoint paths from to for each vertex  ∈  − . It is known that the problem is not approximable within a ratio of (ln ∑ ()), unless NP has an ()-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and  = 4 holds, then the problem is NP-hard, where  =  max {() | ∈ }.

In this paper, we consider the problem in the case where every vertex has a uniform cost. We propose a simple greedy algorithm for delivering a max { + 1,2 − 6}-approximate solution to the problem in time. Especially, in the case of  ≤ 4, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to  ≤ 4.

The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity (), where is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem.

We introduces the , a generalization of the notion of graph module. The theory we develop captures among others undirected graphs, tournaments, digraphs, and 2 −structures. We show that, under some axioms, a unique decomposition tree exists for umodules. Polynomial-time algorithms are provided for: non-trivial umodule test, maximal umodule computation, and decomposition tree computation when the tree exists. Our results unify many known decomposition like modular and bi-join decomposition of graphs, and a new decomposition of tournaments.

Given a set of searchers in the grid, whose search paths are known in advance, can a target that moves at the same speed as the searchers escape detection indefinitely? We study the number of searchers against which the target can still escape. This is less than in an × grid, since a row of searchers can sweep the allowed region.

In an alternating move model where at each time first all searchers move and then the target moves, we show that a target can always escape searchers and there is a strategy for searchers to catch the target. This improves a recent bound  [5] in the simultaneous move model. We also prove similar bounds for the continuous analogue, as well as for searchers and targets moving with different speeds. In the proof, we use a new isoperimetric theorem for subsets of the × grid, which is of independent interest.

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set of disjoint 2-D segments, find a spanning network with minimum size so that for any pair of points in , there exists a path in with length no more than times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, and interval cover), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set of Steiner points in , then construct a point spanner for them. Our algorithm runs in (|| +  log) time, where is the set of Steiner points. We show that is an (1)-approximation in terms of its size when is relatively “well” separated by a constant. For arbitrary rectilinear segments under distance, the approximation ratio improves to 2.

Let be a polygonal cycle on vertices in the plane. A randomized algorithm is presented which computes in ( log) expected time, the edge of whose removal results in a polygonal path of smallest possible dilation. It is also shown that the edge whose removal gives a polygonal path of largest possible dilation can be computed in ( log) time. If is a convex polygon, the running time for the latter problem becomes (). Finally, it is shown that for each edge of , a (1 − )-approximation to the dilation of the path  ∖ {} can be computed in ( log) total time.