Catálogo de publicaciones - libros

We show that isomorphism testing of -trees is in the class StUSPACE(log) (strongly unambiguous logspace). This bound follows from a deterministic logspace algorithm that accesses a strongly unambiguous logspace oracle for canonizing -trees. Further we give a logspace canonization algorithm for -paths.

Given a sequence of real numbers  = (,,...,), two integers and with 1 ≤  ≤  ≤ , and a score function :IR×IR→IR, the is to find a segment [,] = (,,...,) maximizing subject to  −  + 1 ∈ [,]. In this paper, we solve the for the case where the given score function for any constant  > 1. Our algorithm runs in time, where (′) is the time required to solve the all-pairs shortest paths problem on a graph of ′ nodes. By the latest result of Chan [7], , so our algorithm runs in subquadratic time . Lipson  . [21] studied a more restricted case where the score function and there are no length constraints, i.e.,  = 1 and  = . They also showed how to apply their algorithm to analyzing DNA copy number data. However, their algorithm takes () time in the worst situation. Since the length lower bound for the case considered by Lipson  . is a constant, our algorithm solves it in () time.

Given a text of length , the classical indexing problem for pattern matching is to build an index for so that for any query pattern , we can report efficiently all occurrences of in . Cole et al (2004) extended this problem to allow don’t care characters (wildcards) in the text and pattern, and they gave the first index that supports efficient pattern matching. The space complexity of this index is linear in (text length) but exponential in terms of the number of wildcards. Motivated by bioinformatics applications, we investigate indexes whose size depends on only. In the literature, space efficient indexes for wildcard matching are known only for the special case when wildcards appear only in the pattern (Iliopoulos and Rahman, 2007); the space required is (). Not much has been heard for the case when wildcards appear in the text only, or in both the text and pattern. In this paper we give an () space index to support efficient wildcard matching in all three cases. Our solution to the pattern-only case improves the matching time of the previous work tremendously in practice. In addition, our solution can be extended to handle optional wildcards, each of which can match zero or one character.

We study the following fault tolerant variant of the interval group testing model: Given four positive integers , , , , determine the minimum number of questions needed to identify a (possibly empty) set  ⊆ {1,2,..., } (|| ≤ ), under the following constraints. Questions have the form “Is  ∩  ≠ ∅?”, where can be any interval in {1,2..., }. Questions are to be organized in batches of non-adaptive questions (stages), i.e, questions in a given batch can be formulated relying only on the information gathered with the answers to the questions in the previous batches. Up to of the answers can be erroneous or lies.

The study of interval group testing is motivated by several applications. remarkably, to the problem of identifying splice sites in a genome. In particular, such application motivates to focus algorithms that are fault tolerant to some degree and organize the questions in few stages, i.e., on the cases when is small, typically not larger than 2. To the best of our knowledge, we are the first to consider fault tolerant strategies for interval group testing.

We completely characterize the fully non-adaptive situation and provide tight bounds for the case of two batch strategies. Our bounds only differ by a factor of for the case  = 1 and at most 2 in the general case.

Finding the similarity between two sequences is a major problem in computer science. It is motivated by many issues from computational biology as well as from information retrieval and image processing. These fields take into account possible corruptions of the data caused by genome rearrangements, typing mistakes, and more. Therefore, many applications do not require merely complete resemblance of the sequences, but rather an approximated matching. We consider mismatches and swaps as natural mistakes which are allowed in a meagre number. The edit distance problem with swap and mismatch operations was discussed by Amir et. al. [3]. They solved the problem in time. From then on the problem of string matching with at most swaps and mismatches errors was open.

In this paper we present an algorithm that finds all locations where the pattern has at most mismatch and swap errors in time .

In this paper we investigate how graph problems that are NP-hard in general, but polynomially solvable on split graphs, behave on input graphs that are close to being split. For this purpose we define split+  and split+  graphs to be the graphs that can be made split by removing at most edges and at most vertices, respectively. We show that problems like treewidth and minimum fill-in are fixed parameter tractable with parameter on split+  graphs. Along with positive results of fixed parameter tractability of several problems on split+  and split+  graphs, we also show a surprising hardness result. We prove that computing the minimum fill-in of split+  graphs is NP-hard even for  = 1. This implies that also minimum fill-in of chordal+  graphs is NP-hard for every . In contrast, we show that the treewidth of split+ 1 graphs can be computed in polynomial time. This gives probably the first graph class for which the treewidth and the minimum fill-in problems have different computational complexity.

From the analysis of algorithms for probabilistic networks, it is known that a tree decomposition of the minimum treewidth may not be optimal for these algorithms. Instead of treewidth, we consider therefore the weighted treewidth of a weighted graph. In this paper, we present a number of heuristics for determining upper and lower bounds on the weighted treewidth, and a branch and bound algorithm for finding the exact weighted treewidth for weighted graphs.

Given a -regular bipartite graph , whose nodes are divided in nodes and nodes according to the partition, we consider the problem of computing the spanning tree of with the maximum number of black leaves. We prove that the problem is NP hard for any fixed  ≥ 4 and we present a simple greedy algorithm that gives a constant approximation ratio for the problem. More precisely our algorithm can be used to get in linear time an approximation ratio of 2 − 2/( − 1) for  ≥ 4. When applied to cubic bipartite graphs the algorithm only achieves a 2-approximation ratio. Hence we introduce a local optimization step that allows us to improve the approximation ratio for cubic bipartite graphs to 1.5.

Focusing on structural properties, the analysis of our algorithm proves a lower bound on (,), i.e., the minimum such that every with black nodes has a spanning tree with at least black leaves. In particular, for  = 3 we prove that (,3) is exactly .

In an edge deletion problem one is asked to delete at most  edges from a given graph such that the resulting graph satisfies a certain property. In this work, we study four NP-complete edge deletion problems where the goal graph has to be a chain, a split, a threshold, or a co-trivially perfect graph, respectively. All these four graph classes are characterized by a common forbidden induced subgraph 2, that is, an independent pair of edges. We present the seemingly first non-trivial algorithmic results for these four problems, namely, four polynomial-time data reduction algorithms that achieve problem kernels containing (), (), (), and () vertices, respectively.