Catálogo de publicaciones - libros

We divide a string into k segments, each with only one sort of symbols, so as to minimize the total number of exceptions. Motivations come from machine learning and data mining. For binary strings we develop a linear-time algorithm for any k . Key to efficiency is a special-purpose data structure, called W-tree, which reflects relations between repetition lengths of symbols. Existence of algorithms faster than obvious dynamic programming remains open for non-binary strings. Our problem is also equivalent to finding weighted independent sets of prescribed size in paths. We show that this problem in bounded-degree graphs is FPT.

Cographs are those graphs without induced path on four vertices. A graph G is a probe cograph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and G can be extended to a cograph by adding edges between certain non-probes. A partitioned probe cograph is a probe cograph with a given partition in N and P . We characterise probe cographs in several ways. Moreover, we characterise partitioned probe cographs in terms of five forbidden induced subgraphs. Using the forbidden induced subgraph characterisation, we give a linear-time recognition algorithm for probe cographs, improving the recent quadratic-time recognition algorithm by Chandler et al. Our algorithm is a modification of the linear-time recognition algorithm for cographs by Corneil et al.

Polygon-circle graphs (PC-graphs) are defined as intersection graphs of polygons inscribed into a circle, graphs of interval filaments (IFA-graphs) are intersection graphs of curves with both endpoints on prescribed line (filament), filaments above two disjoint intervals must not intersect each other. Recognition of these classes has been a long outstanding open problem. We prove that it is NP-complete to recognize both classes.

A circular-arc model $ {\mathcal {M}} =(C,\mathcal{A})$ is a circle C together with a collection $\mathcal{A}$ of arcs of C . If no arc is contained in any other then $\mathcal{M}$ is a proper circular-arc model, if every arc has the same length then $\mathcal{M}$ is a unit circular-arc model and if $\mathcal{A}$ satisfies the Helly Property then $\mathcal{M}$ is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm.

The pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G . Although pathwidth is a well-known and well-studied graph parameter, there are extremely few graph classes for which pathwidh is known to be tractable in polynomial time. We give in this paper an $\mathcal{O}(n^2)$ -time algorithm computing the pathwidth of circular-arc graphs.

Kelly-width is a parameter of directed graphs recently proposed by Hunter and Kreutzer as a directed analogue of treewidth. We give several alternative characterizations of directed graphs of bounded Kelly-width in support of this analogy. We apply these results to give the first polynomial-time algorithm recognizing directed graphs of Kelly-width 2. For an input directed graph  G  = ( V , A ) the algorithm will output a vertex ordering and a directed graph  H  = ( V , B ) with A  ⊆  B witnessing either that G has Kelly-width at most 2 or that G has Kelly-width at least 3, in time linear in H .

We prove new structural properties for tree-decompositions of planar graphs that we use to improve upon the runtime of tree-decomposition based dynamic programming approaches for several NP-hard planar graph problems. We give for example the fastest algorithm for Planar Dominating Set of runtime 3^tw · n ^ O (1), when we take the treewidth tw as the measure for the exponential worst case behavior. We also introduce a tree-decomposition based approach to solve non-local problems efficiently, such as Planar Hamiltonian Cycle in runtime 6^tw · n ^ O (1). From any input tree-decomposition, we compute in time O ( nm ) a tree-decomposition with geometric properties, which decomposes the plane into disks, and where the graph separators form Jordan curves in the plane.

In the Planar +  k vertex problem the task is to find at most k vertices whose deletion makes the given graph planar. The graphs for which there exists a solution form a minor closed class of graphs, hence by the deep results of Robertson and Seymour [19,18], there is an O ( n ^3) time algorithm for every fixed value of k . However, the proof is extremely complicated and the constants hidden by the big-O notation are huge. Here we give a much simpler algorithm for this problem with quadratic running time, by iteratively reducing the input graph and then applying techniques for graphs of bounded treewidth.

We show that the mixed search number and the linear-width of interval graphs and of split graphs can be computed in linear time and in polynomial time, respectively.

The computation of all minimal transversals of a given hypergraph in output-polynomial time is a long standing open question known as the transversal hypergraph generation. One of the first attempts on this problem—the sequential method [Ber89]—is not output-polynomial as was shown by Takata [Tak02]. Recently, three new algorithms improving the sequential method were published and experimentally shown to perform very well in practice [BMR03, DL05, KS05]. Nevertheless, a theoretical worst-case analysis has been pending. We close this gap by proving lower bounds for all three algorithms. Thereby, we show that none of them is output-polynomial.