A linear time algorithm for finding a maximum independent set of a fullerene

DOI10.4310/JOC.2017.V8.N2.A2zbMATH Open1367.05201OpenAlexW2588150890MaRDI QIDQ2364862FDOQ2364862

Authors: Sean Daugherty, Wendy Myrvold 

Publication date: 25 July 2017

Published in: Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4310/joc.2017.v8.n2.a2

Recommendations

• The independence numbers of fullerenes and benzenoids
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Closed formulas for the number of small paths, independent sets and matchings in fullerenes

zbMATH Keywords

fullerenesmaximum independent set algorithm

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (3)

• The independence numbers of fullerenes and benzenoids
• PentHex puzzles. A reliable and efficient top-down approach to fullerene-structure enumeration
• Backtracking to compute the closed-shell independence number of a fullerene

This page was built for publication: A linear time algorithm for finding a maximum independent set of a fullerene

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2364862)