Linear time construction of 5-phylogenetic roots for tree chordal graphs

doi:10.1007/s10878-008-9164-y

CSpace > 应用数学研究所

	Linear time construction of 5-phylogenetic roots for tree chordal graphs
	Kennedy, William S.3; Kong, Hui 2; Lin, Guohui 1; Yan, Guiying2
	2010
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	19 期号:1 页码:94-106
摘要	Inspired by phylogenetic tree construction in computational biology, Lin et al. (The 11th Annual International Symposium on Algorithms and Computation (ISAAC 2000), pp. 539-551, 2000) introduced the notion of a k -phylogenetic root. A k-phylogenetic root of a graph G is a tree T such that the leaves of T are the vertices of G, two vertices are adjacent in G precisely if they are within distance k in T, and all non-leaf vertices of T have degree at least three. The k-phylogenetic root problem is to decide whether such a tree T exists for a given graph G. In addition to introducing this problem, Lin et al. designed linear time constructive algorithms for ka parts per thousand currency sign4, while left the problem open for ka parts per thousand yen5. In this paper, we partially fill this hole by giving a linear time constructive algorithm to decide whether a given tree chordal graph has a 5-phylogenetic root; this is the largest class of graphs known to have such a construction.
关键词	Graph algorithms Phylogenetic roots Leaf roots Steiner roots Chordal graphs Linear time recognition
DOI	10.1007/s10878-008-9164-y
语种	英语
资助项目	NSERC ; NNSF[10721101] ; NNSF[10531070] ; CFI
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000273402400008
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/11085
专题	应用数学研究所
通讯作者	Lin, Guohui
作者单位	1.Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada 2.Acad Math & Syst Sci, Beijing 100080, Peoples R China 3.McGill Univ, Dept Math, Discrete Math Grp, Montreal, PQ H3A 2A7, Canada
推荐引用方式 GB/T 7714	Kennedy, William S.,Kong, Hui,Lin, Guohui,et al. Linear time construction of 5-phylogenetic roots for tree chordal graphs[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2010,19(1):94-106.
APA	Kennedy, William S.,Kong, Hui,Lin, Guohui,&Yan, Guiying.(2010).Linear time construction of 5-phylogenetic roots for tree chordal graphs.JOURNAL OF COMBINATORIAL OPTIMIZATION,19(1),94-106.
MLA	Kennedy, William S.,et al."Linear time construction of 5-phylogenetic roots for tree chordal graphs".JOURNAL OF COMBINATORIAL OPTIMIZATION 19.1(2010):94-106.