Search

Let C denote a set of n mobile clients, each of which follows a continuous trajectory on a weighted tree T. We establish tight bounds on the maximum relative velocity of the 1-centre and 2-centre of C. When each client in C moves with linear motion along a path on T we derive a tight bound of Θ(n) on the complexity of the motion of the 1-centre and corresponding bounds of O(n2α(n)) and Ω(n2) for a 2-centre, where α(n) denotes the inverse Ackermann function. We describe efficient algorithms for calculating the trajectories of the 1-centre and 2-centre of C: the 1-centre can be found in optimal time O(n logn) when the distance function between mobile clients is known or O(n2) when the function must be calculated, and a 2-centre can be found in time O(n2 logn). These algorithms lend themselves to implementation within the framework of kinetic data structures, resulting in structures that are compact, efficient, responsive, and local. [ABSTRACT FROM AUTHOR]

The problem of maintaining a representation of a dynamic graph as long as a certain property is satisfied has recently been considered for a number of properties. This paper presents an optimal algorithm for this problem on vertex-dynamic connected distance hereditary graphs: both vertex insertion and deletion have complexity O(d), where d is the degree of the vertex involved in the modification. Our vertex-dynamic algorithm is competitive with the existing linear time recognition algorithms of distance hereditary graphs, and is also simpler. Besides, we get a constant time edge-dynamic recognition algorithm. To achieve this, we revisit the split decomposition by introducing graph-labelled trees. Doing so, we are also able to derive an intersection model for distance hereditary graphs, which answers an open problem. [ABSTRACT FROM AUTHOR]

Branchwidth is a connectivity parameter of graphs closely related to treewidth. Graphs of treewidth at most k can be generated algorithmically as the subgraphs of k-trees. n this paper, we investigate the family of edge-maximal graphs of branchwidth k, that we call k-branches. The k-branches are, just as the k-trees, a subclass of the chordal graphs where all minimal separators have size k. However, a striking difference arises when considering subgraph-minimal members of the family. Whereas Kk+1 is the only subgraph-minimal k-tree, we show that for any k ≥7 a minimal k-branch having q maximal cliques exists for any value of $q \not\in \{3,5\}$, except for k=8,q=2. We characterize subgraph-minimal k-branches for all values of k. Our investigation leads to a generation algorithm, that adds one or two new maximal cliques in each step, producing exactly the k-branches. [ABSTRACT FROM AUTHOR]

It is generally acknowledged that integration of large-scale information systems is a challenging problem. A domain that particularly encounters this problem currently is healthcare, where information systems tend to be heterogeneous and in constant evolution. A particular need for health professionals is the ability to ask medical questions across a heterogeneous information system, then visualise and analyse the results in a synthetic and coherent manner. In this paper, we present a case study of a heterogeneous data source search meta-engine framework, based on category theory. This framework addresses the problem of cross-interrogation of heterogeneous data sources, such as relational database management systems, documentary database systems, or collections of documents. It additionally attempts to address the problem of constant evolution of such information systems. The framework has been successfully applied to the biomedical data of the medical information system at the Institut Curie, a major French cancer care centre. Different aspects of this work are illustrated, such as the mathematical foundations of the Prométhée framework, the methodology used for its implementation, and the impact that Prométhée has encountered since its deployment in a hospital environment. [ABSTRACT FROM AUTHOR]

Given a set of leaf-labelled trees with identical leaf sets, the well-known MAST problem consists of finding a subtree homeomorphically included in all input trees and with the largest number of leaves. MAST and its variant called MCT are of particular interest in computational biology. This paper presents positive and negative results on the approximation of MAST, MCT and their complement versions, denoted CMAST and CMCT. For CMAST and CMCT on rooted trees we give 3-approximation algorithms achieving significantly lower running times than those previously known. In particular, the algorithm for CMAST runs in linear time. The approximation threshold for CMAST, resp. CMCT, is shown to be the same whenever collections of rooted trees or of unrooted trees are considered. Moreover, hardness of approximation results are stated for CMAST, CMCT and MCT on small number of trees, and for MCT on unbounded number of trees. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of conservation of combinatorial structures in genome rearrangement scenarios. We characterize a class of signed permutations for which one can compute in polynomial time a reversal scenario that conserves all common intervals, and that is parsimonious among such scenarios. Figeac and Varré (WABI 2004) announced that the general problem is NP-hard. We show that there exists a class of permutations for which this computation can be done in linear time with a very simple algorithm, and, for a larger class of signed permutations, the computation can be achieved in subquadratic time. We apply these methods to permutations obtained from the X chromosomes of the human, mouse and rat. [ABSTRACT FROM AUTHOR]

We provide new tools, such as k-troikas and good subtree-representations, that allow us to give fast and simple algorithms computing branchwidth. We show that a graph G has branchwidth at most k if and only if it is a subgraph of a chordal graph in which every maximal clique has a k-troika respecting its minimal separators. Moreover, if G itself is chordal with clique tree T then such a chordal supergraph exists having clique tree a minor of T. We use these tools to give a straightforward O(m+n+q2) algorithm computing branchwidth for an interval graph on m edges, n vertices and q maximal cliques. We also prove a conjecture of F. Mazoit [13] by showing that branchwidth is polynomial on a chordal graph given with a clique tree having a polynomial number of subtrees. [ABSTRACT FROM AUTHOR]

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs. [ABSTRACT FROM AUTHOR]

In 2000, T. Uno and M. Yagiura published an algorithm that computes all the K common intervals of two given permutations of length n in time. Our paper first presents a decomposition approach to obtain a compact encoding for common intervals of d permutations. Then, we revisit T. Uno and M. Yagiura's algorithm to yield a linear time algorithm for finding this encoding. Besides, we adapt the algorithm to obtain a linear time modular decomposition of an undirected graph, and thereby propose a formal invariant-based proof for all these algorithms. [ABSTRACT FROM AUTHOR]

This paper presents an optimal fully-dynamic recognition algorithm for directed cographs. Given the modular decomposition tree of a directed cograph G, the algorithm supports arc and vertex modification (insertion or deletion) in $\mathcal{O}(d)$ time where d is the number of arcs involved in the operation. Moreover, if the modified graph remains a directed cograph, the modular tree decomposition is updated; otherwise, a certificate is returned within the same complexity. [ABSTRACT FROM AUTHOR]

Determining the diameter of a graph is a fundamental graph operation, yet no efficient (i.e. quadratic time) algorithm is known. In this paper, we examine the diameter problem on chordal and AT-free graphs and show that a very simple (linear time) 2-sweep Lex-BFS algorithm identifies a vertex of maximum eccentricity unless the given graph has a specified induced subgraph (it was previously known that a single Lex-BFS algorithm is guaranteed to end at a vertex that is within 1 of the diameter for chordal and AT-free graphs). As a consequence of the forbidden induced subgraph result on chordal graphs, our algorithm is guaranteed to work optimally for directed path graphs (it was previously known that a single LexBFS algorithm is guaranteed to work optimally for interval graphs). [ABSTRACT FROM AUTHOR]