Premium
The maximum independent set problem for cubic planar graphs
Author(s) -
Burns James E.
Publication year - 1989
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230190307
Subject(s) - combinatorics , mathematics , independent set , planar graph , cubic graph , planar straight line graph , planar , maximal independent set , graph , discrete mathematics , polyhedral graph , 1 planar graph , chordal graph , line graph , computer science , voltage graph , computer graphics (images)
A maximum independent set of a graph is a set of vertices with maximum cardinality such that no pair of vertices is connected by an edge. Choukhmane and Franco have presented a polynomial time approximation algorithm for the maximum independent set problem in cubic planar graphs. If M is taken as the ratio of the size of the independent set produced by their algorithm to the size of a maximum independent set of the input graph, then they show that their algorithm gives M ⩾ 6/7 for any cubic planar graph and M ⩾ 7/8 for a triangle‐free cubic planar graph. We give a new, stronger proof of thier result. The new proof shows that their algorithm actually gives M ⩾ 7/8 for all cubic planar graphs.