Journal of Combinatorics
Volume 8 (2017)
A linear time algorithm for finding a maximum independent set of a fullerene
Pages: 255 – 287
A fullerene is an all carbon molecule that can be represented by a 3-regular planar graph with face sizes five or six. A subset $S$ of the vertices of a graph forms an independent set if the vertices of $S$ are pairwise non-adjacent. The problem of finding the size of a maximum independent set of a graph is NP-complete when restricted to 3-regular graphs. In contrast, for fullerenes we have designed an algorithm that solves the problem in linear time.
maximum independent set algorithm, fullerenes
2010 Mathematics Subject Classification
Primary 05C69, 05C85. Secondary 05C10.