Catálogo de publicaciones - libros

In this paper we consider a generalization of the edge dominating set (EDS) problem, in which each edge needs to be covered times and refer to this as the -EDS problem. We present an exact linear time primal dual algorithm for the weighted -EDS problem on trees with ∈ {0,1}, and our algorithm generates an optimal dual solution as well. We also present an exact linear time algorithm for the unweighted -EDS problem on trees. For general graphs we exhibit a relationship between this problem and the maximum weight matching problem. We exploit this relationship to show that a known linear time -approximation algorithm for the weighted matching problem is also a 2-approximation algorithm for the unweighted -EDS problem on general graphs.

Let be an embedded planar graph whose edges may be curves. The between two points, and (on edges or vertices) of , is the ratio between the shortest path in between and and their Euclidean distance. The supremum over all pairs of points of all these ratios is called the of . Our research is motivated by the problem of designing graphs of low dilation. We provide a characterization of closed curves of constant halving distance (i.e., curves for which all chords dividing the curve length in half are of constant length) which are useful in this context. We then relate the halving distance of curves to other geometric quantities such as area and width. Among others, this enables us to derive a new upper bound on the geometric dilation of closed curves, as a function of /, where and are the diameter and width, respectively. We further give lower bounds on the geometric dilation of polygons with sides as a function of . Our bounds are tight for centrally symmetric convex polygons.

It is shown that for any orthogonal subdivision of size in a -dimensional Euclidean space, ∈ ℕ, ≥ 2, there is an axis-parallel line that stabs at least Ω(log) boxes. For any integer , 1≤ <, there is also an axis-aligned -flat that stabs at least Ω(log) boxes of the subdivision. These bounds cannot be improved.

Let be a set of moving points in the plane. We present a kinetic and dynamic (randomized) data structure for maintaining the convex hull of . The structure uses () space, and processes an expected number of (()log ) critical events, each in (log) expected time, including () insertions, deletions, and changes in the flight plans of the points. Here is the maximum number of times where any specific triple of points can become collinear, ()=() / , and () is the maximum length of Davenport-Schinzel sequences of order on symbols. Compared with the previous solution of Basch et al.[2], our structure uses simpler certificates, uses roughly the same resources, and is also dynamic.

Given a forest = (,) and a positive integer , we consider the problem of finding a minimum number of new edges ′ such that in the augmented graph = (, ∪ ′) any pair of vertices can be connected by two vertex-disjoint paths of length ≤ . We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4.

As defined by Muller (Muller, Ph.D. thesis, Georgia Tech, 1988) and Kannan, Naor, and Rudich (Kannan et al., SIAM J Disc Math, 1992), an labels the vertices of a graph so the adjacency of two vertices can be deduced implicitly from their labels. In general, the labels used in adjacency labelling schemes cannot be tweaked to reflect small changes in the graph.

Motivated by the necessity for further exploration of dynamic (implicit) adjacency labelling schemes we introduce the concept of error detection, discuss metrics for judging the quality of such dynamic schemes, and develop a dynamic scheme for line graphs that allows the addition and deletion of vertices and edges. The labels used in this scheme require (log ) bits and updates can be performed in () time, where is the number of edges added to or deleted from the line graph. This compares to the best known (static) adjacency labelling scheme for line graphs which uses (log ) bit labels and requires Θ() time to generate a labelling even when provided with the line graph representation.

We consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the version, in which the salesman is required to return in the city where it started from, we give a -competitive algorithm and prove that this is best possible. For the version, the on-line analogue of the shortest asymmetric hamiltonian path problem, we show that the competitive ratio of any on-line algorithm has to depend on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are , that is, in which the salesman cannot stay idle when some city can be served.

We describe an (/log )-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (1976), Takaoka (1992), Dobosiewicz (1990), Han (2004), Takaoka (2004), and Zwick (2004). The new algorithm is surprisingly simple and different from previous ones.

We study the shortest path problem in weighted polygonal subdivisions of the plane, with the additional constraint of an upper bound, , on the number of links (segments) in the path. We prove structural properties of optimal paths and utilize these results to obtain approximation algorithms that yield a path having () links and weighted length at most (1+) times the weighted length of an optimal -link path, for any fixed > 0. Some of our results make use of a new solution for the 1-link case, based on computing optimal solutions for a special sum-of-fractionals (SOF) problem. We have implemented a system, based on the CORE library, for computing optimal 1-link paths; we experimentally compare our new solution with a previous method for 1-link optimal paths based on a prune-and-search scheme.

We study the problem of non-preemptive scheduling to minimize energy consumption for devices that allow dynamic voltage scaling. Specifically, consider a device that can process jobs in a non-preemptive manner. The input consists of (i) the set of available speeds of the device, (ii) a set of jobs, and (iii) a precedence constraint Π among . Each job in , defined by its arrival time , deadline , and amount of computation , is supposed to be processed by the device at a speed in . Under the assumption that a higher speed means higher energy consumption, the power-saving scheduling problem is to compute a feasible schedule with speed assignment for the jobs in such that the required energy consumption is minimized.

This paper focuses on the setting of dynamic voltage scaling, i.e., speed change is not allowed in the middle of processing a job. To demonstrate that this restriction on many portable power-aware devices introduces hardness to the power-saving scheduling problem, we prove that the problem is NP-hard even if = and = hold for all , ′∈ ||=2. If ||<∞, we also give fully polynomial-time approximation schemes for two cases of the general NP-hard problem: (a) all jobs share a common arrival time, and (b) Π = ∅ and for any , ′ ∈ , ≤ implies ≤ . To the best of our knowledge, there is no previously known approximation algorithm for any special case of the NP-hard problem.