期刊
INFORMATION AND COMPUTATION
卷 255, 期 -, 页码 126-146出版社
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2017.06.001
关键词
Exact algorithm; Independent set; Graph; Polynomial-space; Branch-and-reduce; Measure-and-conquer; Amortized analysis
资金
- NFSC of China [61370071]
- Fundamental Research Funds for the Central Universities [ZYGX2012J069]
- Grants-in-Aid for Scientific Research [17K00014] Funding Source: KAKEN
We show that the maximum independent set problem on an n-vertex graph can be solved in 1.1996(n)n(0)(1) time and polynomial space, which even is faster than Robson's 1.2109(n)n(0)(1) -time exponential-space algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7, which run in time of 1.1893(n)n(0)(1) and 1.1970(n)n(0)(1), respectively. Our algorithms are obtained by using fast algorithms for MIS in low-degree graphs in a hierarchical way and making a careful analysis on the structure of bounded-degree graphs. (C) 20 17 Elsevier Inc. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据