Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875456 | Theoretical Computer Science | 2018 | 6 Pages |
Abstract
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(n2)-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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Xingfu Li, Haodi Feng, Haotao Jiang, Binhai Zhu,