AN OPTIMAL ALGORITHM FOR FINDING A MAXIMUM INDEPENDENT SET OF A CIRCULAR-ARC GRAPH

作     者：MASUDA, S NAKAJIMA, K 

作者机构：UNIV MARYLAND SYST RES CTR COLLEGE PK MD 20742 USA 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (SIAM J Comput)

年 卷 期：1988年第17卷第1期

页      面：41-52页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：68C25 68E10 optimal algorithm circular-arc graph maximum independent set 

摘      要：A new algorithm is presented for finding a maximum independent set of a circular-arc graph. When the graph is given in the form of a family of n arcs, our algorithm requires only O(nlogn) role=presentationO(n⋅logn)span style=display: inline-block; overflow: hidden; vertical-align: -0.352em; border-left: 0px solid; width