Incremental algorithms for the maximum internal spanning tree problem  

作　　者：Xianbin ZHU Wenjun LI Yongjie YANG Jianxin WANG 

机构地区：[1]School of Computer Science and Engineering,Central South University,Changsha 410083,China [2]Chair of Economic Theory,Saarland University,Saarbrucken 66123,Germany [3]Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation,Changsha University of Science and Technology,Changsha 410114,China

出　　处：《Science China(Information Sciences)》2021年第5期73-80,共8页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant Nos.61672536,61502054,61702557,61420106009,61872048,61872450,61828205);Hunan Provincial Science and Technology Program(Grant No.2018WK4001);Natural Science Foundation of Hunan Province(Grant No.2017JJ3333);Scientific Research Fund of Hunan Provincial Education Department(Grant No.17C0047);China Postdoctoral Science Foundation(Grant No.2017M612584);Postdoctoral Science Foundation of Central South University。

摘　　要：The maximum internal spanning tree(MIST)problem is utilized to determine a spanning tree in a graph G,with the maximum number of possible internal vertices.The incremental maximum internal spanning tree(IMIST)problem is the incremental version of MIST whose feasible solutions are edge-sequences e_(1),e_(2),…,e_(n-1) such that the first k edges form trees for all k∈[n-1].A solution’s quality is measured using max_(k∈[n-1])opt(G,k)/|In(T_(k))|with lower being better.Here,opt(G,k)denotes the number of internal vertices in a tree with k edges in G,which has the largest possible number of internal vertices,and|In(Tk)|is the number of internal vertices in the tree comprising the solution’s first k edges.We first obtained an IMIST algorithm with a competitive ratio of 2,followed by a 12/7-competitive algorithm based on an approximation algorithm for MIST.

关 键 词：maximum internal spanning tree incremental problem approximation algorithm competitive ratio 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]