Premium
An approximation algorithm for the maximum independent set problem in cubic planar graphs
Author(s) -
Choukhmane Elarbi,
Franco John
Publication year - 1986
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.3230160402
Subject(s) - combinatorics , planar , planar graph , independent set , mathematics , maximal independent set , planar straight line graph , cubic graph , approximation algorithm , set (abstract data type) , discrete mathematics , graph , polyhedral graph , 1 planar graph , chordal graph , computer science , line graph , voltage graph , computer graphics (images) , programming language
A polynomial time approximation algorithm A for the problem of finding a maximal independent set for cubic planar graphs is presented. It is shown that M A > 6/7 in the case of cubic planar graphs and M A = 7/8 in the case of triangle free cubic planar graphs where M A is the worst‐case ratio of the size of the independent set found by A to the size of the maximum independent set for the graph input to A .