Advertisement

In the past ** Michael Fellows** has collaborated on articles with

More information about

AbstractA galaxy is a union of vertex disjoint stars. The galactic number of a graph is the minimum number of galaxies which partition the edge set. The galactic number of complete graphs is determined. This result is used to give bounds on the galactic number of binary cube graphs. The problem of determining the galactic number of a graph is shown to be NP-complete.

AbstractTwo natural kinds of problems about “structured collections of symbols” can be generally referred to as the Largest Common Subobject and the Smallest Common Superobject problems, which we consider here as the dual problems of interest. For the case of rooted binary trees where the symbols occur as leaf-labels and a subobject is defined by label-respecting hereditary topological containment, both of these problems are NP-complete, as are the analogous problems for sequences (the well-known Longest Common Subsequence and Shortest Common Supersequence problems). When the trees are restricted by allowing each symbol to occur as a leaf-label at most once (which we call a phylogenetic tree or p-tree), then the Largest Common Subtree problem, better known as the Maximum Agreement Subtree (MAST) problem, is solvable in polynomial time. We explore the complexity of the basic subobject and superobject problems for both sequences and binary trees when the inputs are restricted to p-trees and p-sequences (p-sequences are sequences where each symbol occurs at most once). We prove that the sequence analog of MAST can be solved in polynomial time. The Shortest Common Supersequence problem restricted to inputs consisting of a collection of p-sequences (pSCS) is NP-complete; we show NP-completeness of the analogous Smallest Common Supertree problem restricted to p-trees (pSCT). We also show that both problems are hard for the parameterized complexity classes W[1] where the parameter is the number of input objects. We prove fixed-parameter tractability for pSCS and pSCT when the k input objects are restricted to be complete: every symbol of Σ occurs exactly once in each object and the question is whether there is a common superobject of size bounded by |Σ|+r and the parameter is the pair (k,r). We show that without this restriction, both problems are harder than Directed Feedback Vertex Set, for which parameterized complexity is famously unresolved.

AbstractThe Mouse Lymphoma Assay (MLA) Workgroup of the International Workshop on Genotoxicity Testing (IWGT), comprised of experts from Japan, Europe and the United States, met on September 9, 2005, in San Francisco, CA, USA. This meeting of the MLA Workgroup was devoted to reaching a consensus on issues involved with 24-h treatment. Recommendations were made concerning the acceptable values for the negative/solvent control (mutant frequency, cloning efficiency and suspension growth) and the criteria to define an acceptable positive control response. Consensus was also reached concerning the use of the global evaluation factor (GEF) and appropriate statistical trend analysis to define positive and negative responses for the 24-h treatment. The Workgroup agreed to continue their support of the International Committee on Harmonization (ICH) recommendation that the MLA assay should include a 24-h treatment (without S-9) in those situations where the short treatment (3–4 h) gives negative results.

AbstractThe Graph k-Cut problem is that of finding a set of edges of minimum total weight, in an edge-weighted graph, such that their removal from the graph results in a graph having at least k connected components. An algorithm with a running time of O(nk2) for this problem has been known since 1988, due to Goldschmidt and Hochbaum. We show that the problem is hard for the parameterized complexity class W[1]. We also investigate the complexity of a related problem, Cutting A Few Vertices from a Graph, that asks for the minimum cost of separating at least k vertices from an edge-weighted connected graph. We show that this problem also is hard for W[1].

Advertisement