The maximum independent set problem for cubic planar graphs | Zendy

Burns James E. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research