Exact algorithms for maximum independent set

Citation data:

Information and Computation, ISSN: 0890-5401, Vol: 255, Page: 126-146

Publication Year:
2017
Usage 1
Abstract Views 1
Social Media 3
Shares, Likes & Comments 3
Citations 1
Citation Indexes 1
DOI:
10.1016/j.ic.2017.06.001
Author(s):
Mingyu Xiao, Hiroshi Nagamochi
Publisher(s):
Elsevier BV
Tags:
Mathematics, Computer Science
article description
We show that the maximum independent set problem on an n -vertex graph can be solved in 1.1996nnO(1) time and polynomial space, which even is faster than Robson's 1.2109nnO(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.1893nnO(1) and 1.1970nnO(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.

This article has 0 Wikipedia mention.