Premium
An algorithm for finding a large independent set in planar graphs
Author(s) -
Chiba Norishige,
Nishizeki Takao,
Saito Nobuji
Publication year - 1983
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.3230130209
Subject(s) - combinatorics , mathematics , independent set , algorithm , planar graph , graph , set (abstract data type) , wheel graph , computer science , graph power , line graph , programming language
A subset of the vertices of a graph is independent if no two vertices in the set are adjacent. M. O. Albertson proposed an algorithm for finding an independent set that contains more than two‐ninth of the vertices of a planar graph. Refining his algorithm, we give an O (n 2 ) algorithm for the same purpose.