In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalen...
详细信息
In a rooted triangulated planar graph, an outer vertex and two outer edges incident to it are designated as its root, respectively. Two plane embeddings of rooted triangulated planar graphs are defined to be equivalent if they admit an isomorphism such that the designated roots correspond to each other. Given a positive integer n, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted triangulated planar graphs with at most n vertices without delivering two reflectively symmetric copies.
The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-sce...
详细信息
The incongruency between a gene tree and a corresponding species tree can be attributed to evolutionary events such as gene duplication and gene loss. This paper describes a combinatorial model where so-called DTL-scenarios are used to explain the differences between a gene tree and a corresponding species tree taking into account gene duplications, gene losses, and lateral gene transfers (also known as horizontal gene transfers). The reasonable biological constraint that a lateral gene transfer may only occur between contemporary species leads to the notion of acyclic DTL-scenarios. Parsimony methods are introduced by defining appropriate optimization problems. We show that finding most parsimonious acyclic DTL-scenarios is NP-hard. However, by dropping the condition of acyclicity, the problem becomes tractable, and we provide a dynamic programming algorithm as well as a fixed-parameter tractable algorithm for finding most parsimonious DTL-scenarios.
This paper addresses the definition, contouring, and visualization of scalar functions on unorganized point sets, which are sampled from a surface in 3D space;the proposed framework builds on moving least-squares tech...
详细信息
This paper addresses the definition, contouring, and visualization of scalar functions on unorganized point sets, which are sampled from a surface in 3D space;the proposed framework builds on moving least-squares techniques and implicit modeling. Given a scalar function f : P -> R, defined on a point set P, the idea behind our approach is to exploit the local connectivity structure of the k-nearest neighbor graph of P and mimic the contouring of scalar functions defined on triangle meshes. Moving least-squares and implicit modeling techniques are used to extend f from P to the surface M underlying P. To this end, we compute an analytical approximation (f) over tilde of f that allows us to provide an exact differential analysis of (f) over tilde, draw its iso-contours, visualize its behavior on and around M, and approximate its critical points. We also compare moving least-squares and implicit techniques for the definition of the scalar function underlying f and discuss their numerical stability and approximation accuracy. Finally, the proposed framework is a starting point to extend those processing techniques that build on the analysis of scalar functions on 2-manifold surfaces to point sets. (c) 2010 Elsevier Ltd. All rights reserved.
In this paper, a modified group theoretic method is introduced for symmetry analysis of regular structures. A structure is called regular if its model can be formed by one of the graph products. Here, the concepts fro...
详细信息
In this paper, a modified group theoretic method is introduced for symmetry analysis of regular structures. A structure is called regular if its model can be formed by one of the graph products. Here, the concepts from graph products are used in order to simplify the conventional group theoretic analysis of cyclically symmetric structures. The analysis of truss towers under static loads is presented for simple first-order, and geometrically nonlinear second-order effects.
An algorithm is proposed to solve the sensor subset selection problem. In this problem, a prespecified number of sensors are selected to estimate the value of a parameter such that a metric of estimation accuracy is m...
详细信息
An algorithm is proposed to solve the sensor subset selection problem. In this problem, a prespecified number of sensors are selected to estimate the value of a parameter such that a metric of estimation accuracy is maximized. The metric is defined as the determinant of the Bayesian Fisher information matrix (B-FIM). It is shown that the metric can be expanded as a homogenous polynomial of decision variables. In the algorithm, a separable approximation of the polynomial is derived based on a graph-theoretic clustering method. To this end, a graph is constructed where the vertices represent the sensors, and the weights on the edges represent the coefficients of the terms in the polynomial. A process known as natural selection in population genetics is utilized to find the dominant sets of the graph. Each dominant set is considered as one cluster. When the separable approximation is obtained, the sensor selection problem is solved by dynamic programming. Numerical results are provided in the context of localization via direction-of-arrival (DOA) measurements to evaluate the performance of the algorithm.
We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respective...
详细信息
We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respectively, and-in the case of undirected graphs-as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4 (k) nm) on directed graphs and O(poly(n)+4 (k) k (2)) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2 (O(klog k)) poly(n) and O(poly(n)+6.75 (k) poly(k)) respectively.
Genes with a common function are often hypothesized to have correlated expression levels in mRNA expression data, motivating the development of clustering algorithms for gene expression data sets. We observe that exis...
详细信息
Genes with a common function are often hypothesized to have correlated expression levels in mRNA expression data, motivating the development of clustering algorithms for gene expression data sets. We observe that existing approaches do not scale well for large data sets, and indeed did not converge for the data set considered here. We present a novel clustering method TCLUST that exploits coconnectedness to efficiently cluster large, sparse expression data. We compare our approach with two existing clustering methods CAST and K-means which have been previously applied to clustering of gene-expression data with good performance results. Using a number of metrics, TCLUST is shown to be superior to or at least competitive with the other methods, while being much faster. We have applied this clustering algorithm to a genome-scale gene-expression data set and used gene set enrichment analysis to discover highly significant biological clusters. (Source code for TCLUST is downloadable at http://***/similar to bdost/tclust.)
Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial-time algor...
详细信息
Galled trees, directed acyclic graphs that model evolutionary histories with isolated hybridization events, have become very popular due to both their biological significance and the existence of polynomial-time algorithms for their reconstruction. In this paper, we establish to which extent several distance measures for the comparison of evolutionary networks are metrics for galled trees, and hence, when they can be safely used to evaluate galled tree reconstruction methods.
A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in vari...
详细信息
A coloring of a graph is convex if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. We study the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, epsilon-test with query complexity O(k/epsilon (2)) and time complexity O(kn/epsilon). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of n if we allow a preprocessing stage of time O(n) and O(n (2)), respectively. Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1.
Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G = (V, E), two positive integers k and t, and an alphabet E, a feasible...
详细信息
Motivated by applications in software programming, we consider the problem of covering a graph by a feasible labeling. Given an undirected graph G = (V, E), two positive integers k and t, and an alphabet E, a feasible labeling is defined as an assignment of a set L c to each vertex v is an element of V. such that (i) vertical bar L-v vertical bar <= k for all v is an element of V and (ii) each label a is an element of Sigma is used no more than t times. An edge e = {i, j} is said to be covered by a feasible labeling L-i boolean AND L-j not equal empty set. G is said to be covered if there exists a feasible labeling that covers each edge e E E. In general, we show that the problem of deciding whether or not a tree can be covered is strongly NP-complete. For k = 2, t = 3, we characterize the trees that can be covered and provide a linear time algorithm for solving the decision problem. For fixed t, we present a strongly polynomial algorithm that solves the decision problem: if a tree can be covered, then a corresponding feasible labeling can be obtained in time polynomial in k and the size of the tree. For general graphs, we give a strongly polynomial algorithm to resolve the covering problem for k = 2, t = 3. (C) 2011 Elsevier B.V. All rights reserved.
暂无评论