Catálogo de publicaciones - libros

The (LCS) problem is one of the classical and well-studied problems in computer science. The computation of the LCS is a frequent task in DNA sequence analysis, and has applications to genetics and molecular biology. In this paper we define new variants, introducing the notion of gap-constraints in LCS problem and present efficient algorithms to solve them.

Let be a function on pairs of vertices. An for a family of graphs labels the vertices of all graphs in such that for every graph and every two vertices ,∈, (,) can be inferred by merely inspecting the labels of and . The of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in . This paper illustrates that the notion of universal matrices can be used to efficiently construct -labeling schemes.

Let be a family of connected graphs of size at most and let denote the collection of graphs of size at most , such that each graph in is composed of a disjoint union of some graphs in . We first investigate methods for translating -labeling schemes for to -labeling schemes for . In particular, we show that in many cases, given an -labeling scheme of size () for a graph family , one can construct an -labeling scheme of size ()+loglog+(1) for . We also show that in several cases, the above mentioned extra additive term of loglog+(1) is necessary. In addition, we show that the family of -node graphs which are unions of disjoint circles enjoys an adjacency labeling scheme of size log+(1). This illustrates a non-trivial example showing that the above mentioned extra additive term is sometimes not necessary.

We then turn to investigate distance labeling schemes on the class of circles of at most vertices and show an upper bound of 1.5log+(1) and a lower bound of 4/3log–(1) for the size of any such labeling scheme.

A transitive orientation of an undirected graph is an assignment of directions to its edges so that these directed edges represent a transitive relation between the vertices of the graph. Not every graph has a transitive orientation, but every graph can be turned into a graph that has a transitive orientation, by adding edges. We study the problem of adding an inclusion minimal set of edges to an arbitrary graph so that the resulting graph is transitively orientable. We show that this problem can be solved in polynomial time, and we give a surprisingly simple algorithm for it.

This work provides the first detailed investigation of the disturbed diffusion scheme FOS/C introduced in [17] as a type of diffusion distance measure within a graph partitioning framework related to Lloyd’s -means algorithm [14]. After outlining connections to distance measures proposed in machine learning, we show that FOS/C can be related to random walks despite its disturbance. Its convergence properties regarding load distribution and edge flow characterization are examined on two different graph classes, namely torus graphs and distance-transitive graphs (including hypercubes), representatives of which are frequently used as interconnection networks.

In this paper, we consider the problem and develop exact exponential algorithms that break the trivial (2) bound. A simple time algorithm is developed to solve this problem on general graphs. For sparse graphs, e.g. graphs with degree bounded by 3 and 4, we show that a few new branching techniques can be applied to these graphs and the resulting algorithms have time complexities (2) and (2), respectively. All our algorithms only need polynomial space.

We give a polynomial-time oracle algorithm for Tournament Canonization that accesses oracles for Tournament Isomorphism and Rigid-Tournament Canonization. Extending the Babai-Luks Tournament Canonization algorithm, we give an algorithm for canonization and isomorphism testing of -hypertournaments, where is the number of vertices and is the size of hyperedges.

Given a sequence of real numbers = , ,..., and a positive integer , the is to find the segment (,) = , ,..., such that the rank of the sum (, ) = ∑ is over all segments. We present a deterministic algorithm for this problem that runs in ( log) time. The previously best known randomized algorithm for this problem runs in expected ( log) time. Applying this algorithm we can obtain a deterministic algorithm for the , i.e., the problem of enumerating the largest sum segments, that runs in ( log + ) time. The previously best known randomized and deterministic algorithms for the run respectively in expected ( log + ) and ( log + ) time in the worst case.

Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp machine. Roughly speaking, we show that on the two-dimensional grid, the Propp machine always has the same number of tokens on a node as does the random walk in expectation, apart from an additive error of less than eight. This constant is independent of the total number of tokens and the runtime of the two processes. However, we also show that it makes a difference whether the Propp machine serves the neighbors in a circular or non-circular order.

The compressed pattern matching problem is to find all occurrences of a given pattern in a compressed text. In this paper an efficient grammar-based compression algorithm is presented for the compressed pattern matching. The algorithm achieves the worst-case approximation ratio (loglog) for the optimum grammar size with an input text of length . This upper bound improves the complexity of the compressed pattern matching problem to time and (loglog + ) space for any pattern shorter than and the number of pattern occurrences.

We study the (I-KP), and the (I-MCKP), as generalizations of the classic 0/1 knapsack problem (KP) and the multiple-choice knapsack problem (MCKP), respectively. Compared to singleton items in KP and MCKP, each item in I-KP and I-MCKP is represented by a ([ , ], ) pair, where integer interval [, ] specifies the possible range of units, and is the unit-price. Our main results are a FPTAS for I-KP with time ( log + /) and a FPTAS for I-MCKP with time ( /), and pseudo-polynomial-time algorithms for both I-KP and I-MCKP with time () and space ( + ). Here , , and denote number of items, number of item sets, and knapsack capacity respectively. We also present a 2-approximation of I-KP and a 3-approximation of I-MCKP both in linear time.

We apply I-KP and I-MCKP to the single-good multi-unit sealed-bid auction clearing problem where identical units of a single good are auctioned. We focus on two bidding models, among them the interval model allows each bid to specify an interval range of units, and XOR-interval model allows a bidder to specify a set of interval bids. The interval and XOR-interval bidding models correspond to I-KP and I-MCKP respectively, thus are solved accordingly. We also show how to compute VCG payments to all the bidders with an overhead of (log) factor. Our results for XOR-interval bidding model imply for the bidding model studied by Kothari et al. [18], improving their algorithms by a factor of Ω().