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

DOI10.4310/JOC.2017.V8.N2.A2MaRDI QIDQ2364862zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(3)

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

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)