Catálogo de publicaciones - libros

This paper presents an () time algorithm for approximating the unit cost edit distance for ordered and rooted trees of bounded degree within a factor of (), where is the maximum size of two input trees, and the algorithm is based on transformation of an ordered and rooted tree into a string.

A node-labeled rooted tree (with root ) is an all-or-nothing subtree (called ) of a node-labeled rooted tree ′ if (1) is a subtree of the tree rooted at some node (with the same label as ) of ′, (2) for each internal node of , the neighbors of in ′ are the neighbors of in . Tree ′ is then called an of . Given a set of trees, smallest common AoN-supertree problem seeks the smallest possible tree (denoted as ) such that every tree in is an of . It generalizes the smallest superstring problem and it has applications in glycobiology. We present a polynomial-time greedy algorithm with approximation ratio 6.

In the single-sink buy-at-bulk network design problem we are given a subset of source nodes in a weighted undirected graph: each source node wishes to send a given amount of flow to a sink node. Moreover, a set of cable types is given, each characterized by a cost per unit length and by a capacity: the ratio cost/capacity decreases from small to large cables by economies of scale. The problem is to install cables on edges at minimum cost, such that the flow from each source to the sink can be routed simultaneously. The approximation ratio of this NP-hard problem was gradually reduced from (log) to 65.49 by a long series of papers. In this paper, we design a better 24.92 approximation algorithm for this problem.

Suppose that each vertex of a graph is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive “power” from at most one supply vertex through edges in . One thus wishes to partition into connected components so that each component either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in , and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P=NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. The FPTAS can be easily extended for partial -trees, that is, graphs with bounded treewidth.

In a convex drawing of a plane graph, all edges are drawn as straight-line segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graph has a convex drawing if and only if is internally triconnected, and an internally triconnected plane graph has a convex grid drawing on an × grid if is triconnected or the triconnected component decomposition tree () of has two or three leaves, where is the number of vertices in . In this paper, we show that an internally triconnected plane graph has a convex grid drawing on a 2 × grid if () has exactly four leaves. We also present an algorithm to find such a drawing in linear time. Our convex grid drawing has a rectangular contour, while most of the known algorithms produce grid drawings having triangular contours.

A dominating target of a graph =(,) is a set of vertices s.t. for all  ⊆ , if  ⊆  and induced subgraph on is connected, then is a dominating set of . The size of the smallest dominating target is called dominating target number of the graph, (). We provide polynomial time algorithms for , and in dominating-pair graphs (i.e., ()=2). We also give approximation algorithm for with performance ratio 2 on graphs with small dominating targets. This is a significant improvement on ≤( + 2) given by Fomin et.al. [2004] on graphs with small -octopus.

Dominating target, -octopus, Dominating set, Dominating-pair graph, Steiner tree.

We consider the problem of designing efficient algorithms for computing certain matchings in a bipartite graph , with a partition of the edge set as . A is a set of (, ) pairs, such that each and each appears in at most one pair. We first consider the problem; an algorithm to solve the popular matching problem was given in [3], where is the number of vertices and is the number of edges in the graph. Here we present an () randomized algorithm for this problem, where < 2.376 is the exponent of matrix multiplication. We next consider the problem; an algorithm was given in [7] for this problem. Here we give an () randomized algorithm, where is the largest rank of an edge used in such a matching. We also consider a generalization of this problem, called the weighted rank-maximal matching problem, where vertices in have positive weights.

We consider the updatable streaming graph model, where edges of a graph arrive or depart in arbitrary sequence and are processed in an online fashion using sub-linear space and time. We study the problem of estimating aggregate path metrics defined as the number of pairs of vertices that have a simple path between them of length . For a streaming undirected graph with vertices, edges and components, we present an space algorithm for estimating and an space lower bound. We show that estimating over directed streaming graphs, and estimating over streaming graphs (whether directed or undirected), for any ≥3 requires Ω() space. We also present a space lower bound of Ω() for the problems of (a) deterministically testing the connectivity, and, (b) estimating the size of transitive closure, of undirected streaming graphs that allow both edge-insertions and deletions.

Given a triangulation , whose vertex set is a set of points in the plane, and given a real number with 0<<, we design an ()-time algorithm that constructs a connected spanning subgraph ′ of whose maximum degree is at most 14+⌈2/⌉. If is the Delaunay triangulation of , and = 2/3, we show that ′ is a -spanner of (for some constant ) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If is the graph consisting of all Delaunay edges of length at most 1, and = /3, we show that ′ is a -spanner (for some constant ) of the unit-disk graph of , whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25. Finally, if is a triangulation satisfying the diamond property, then for a specific range of values of dependent on the angle of the diamonds, we show that ′ is a -spanner of (for some constant ) whose maximum degree is bounded by a constant dependent on .

We address proximity problems in the presence of roads on the plane. More specifically, we present the first optimal algorithm for constructing the city Voronoi diagram. We apply the continuous Dijkstra paradigm to obtain an optimal algorithm for building a shortest path map for a given source, and then it extends to that for the city Voronoi diagram. Moreover, the algorithm applies to other generalized situations including metric spaces induced by roads and obstacles together.