标题:A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs
作者:Li, Xingfu; Feng, Haodi; Jiang, Haitao; Zhu, Binhai
通讯作者:Li, XF
作者机构:[Li, Xingfu] Shanxi Agr Univ, Sch Software, Jinzhong 030801, Shanxi, Peoples R China.; [Feng, Haodi; Jiang, Haitao] Shandong Univ, Sch Comp Sci & Te 更多
会议名称:10th International Frontiers of Algorithmics Workshop (FAW)
会议日期:JUN 30-JUL 02, 2016
来源:Frontiers in Algorithmics, FAW 2016
出版年:2016
卷:9711
页码:92-101
DOI:10.1007/978-3-319-39817-4_10
关键词:Polynomial; Algorithm; Maximum internal spanning tree; Interval graph
摘要:This paper studies the Maximum Internal Spanning Tree problem which is to find a spanning tree with the maximum number of internal vertices on a graph. We prove that the problem can be solved in polynomial time on interval graphs. The idea is based on the observation that the number of internal vertices in a maximum internal spanning tree is at most one less than the number of edges in a maximum path cover on any graph. On an interval graph, we present an O(n(2))-algorithm to find a spanning tree in which the number of internal vertices is exactly one less than the number of edges in a maximum path cover of the graph, where n is the number of vertices in the interval graph.
收录类别:CPCI-S
WOS核心被引频次:1
资源类型:会议论文
TOP