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

作     者：Li, Peng Shang, Jianhui Shi, Yi 

作者机构：Chongqing Univ Technol Coll Sci Chongqing 400054 Peoples R China Shanghai Jiao Tong Univ Sch Math Sci Shanghai 200240 Peoples R China Shanghai Jiao Tong Univ Bio x Inst Key Lab Genet Dev & Neuropsychiat Disorders Minist Educ 1954 Huashan Rd Shanghai 200030 Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2022年第930卷

页      面：77-85页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China [11701059, 11971311] Natural Science Foundation of Chongqing [cstc2019jcyj-msxmX0156] Natural Science Foundation of Shanghai [20511101900, 20ZR1427200] Youth project of science and technology research program of Chongqing Education Commission of China [KJQN202001130, KJQN202101130] 

主　　题：Linear time algorithm Maximum internal spanning tree Connected interval graphs Normal orderings 

摘      要：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.(c) 2022 Elsevier B.V. All rights reserved.