An approximation algorithm for the maximum independent set problem in cubic planar graphs | Zendy

Choukhmane Elarbi | Zendy; Franco John | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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 .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research