We show that the maximum independent set problem (MIS) on an n-vertex graph can be solved in 1.2002~nnO(1) time and polynomial space, which is even faster than Robson's 1.2109~nnO(1)-time exponentialspace algorithm published in 1986. We also obtain improved algorithms for MIS in graphs with maximum degree 6 and 7. Our algorithms are obtained by effectively using fast algorithms for MIS in low-degree graphs and making careful analyses for MIS in high-degree graphs.
展开▼
