关于树的最大区间子图

On the maximal interval subgraph of a tree.

作者信息

Zhang Haiying, Zhou Bing

机构信息

Department of Mathematics, Trent University, Peterborough, Canada.

出版信息

J Comput Biol. 2010 Oct;17(10):1425-33. doi: 10.1089/cmb.2009.0039.

DOI:10.1089/cmb.2009.0039

PMID:20937015

Abstract

We study the problem of finding the maximum interval subgraph in a tree. This problem is related to the Double Digestion Problem of DNA physical mapping. We show that the complexity of an algorithm of Wang is O(n). We also present a linear algorithm of our own. We study the case when the edges of the tree is weighted as well. An algorithm with complexity O(n³) is presented.

摘要

我们研究在一棵树中寻找最大区间子图的问题。这个问题与DNA物理图谱的双酶切问题相关。我们证明了Wang的一个算法的复杂度为O(n)。我们还给出了一个我们自己的线性算法。我们也研究了树的边带权的情况。给出了一个复杂度为O(n³)的算法。