A simple linear time algorithm to solve the MIST problem on interval graphs

Motivated by the design of cost-efficient communication networks, the problem about Maximum Internal Spanning Tree that arises in a connected graph, is proposed to find a spanning tree with the maximum number of internal vertices. In 2018, Xingfu Li et al. presented a polynomial algorithm to find a maximum internal spanning tree in a connected interval graph. Based on the structure of normal orderings on interval graphs, we present a simple linear time algorithm that solve the problem when restricted to connected interval graphs in this paper. The proof provides additional insight about the linear time algorithm on interval graphs.

Authors

• Peng Li
• Jianhui Shang
• Yi Shi School of Artificial Intelligence, Nanjing University, Nanjing, China; State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China

Keywords

• Linear time algorithm
• Maximum internal spanning tree
• Connected interval graphs
• Normal orderings