The maximum independent set problem for cubic planar graphs
- 1 May 1989
- Vol. 19 (3) , 373-378
- https://doi.org/10.1002/net.3230190307
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- An approximation algorithm for the maximum independent set problem in cubic planar graphsNetworks, 1986
- Approximation algorithms for NP-complete problems on planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- An Approximation Algorithm for the Maximum Independent Set Problem on Planar GraphsSIAM Journal on Computing, 1982
- Extremal bipartite subgraphs of cubic triangle‐free graphsJournal of Graph Theory, 1982
- On maximum bipartite subgraphsJournal of Graph Theory, 1982
- Applications of a Planar Separator TheoremSIAM Journal on Computing, 1980
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Finding a Maximum Cut of a Planar Graph in Polynomial TimeSIAM Journal on Computing, 1975
- On some extremal problems in graph theoryIsrael Journal of Mathematics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965