{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T06:47:27Z","timestamp":1765176447245},"reference-count":7,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":8533,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1983,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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\u2010ninth of the vertices of a planar graph. Refining his algorithm, we give an <jats:italic>O<\/jats:italic>(n<jats:sup>2<\/jats:sup>) algorithm for the same purpose.<\/jats:p>","DOI":"10.1002\/net.3230130209","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T15:18:31Z","timestamp":1178896711000},"page":"247-252","source":"Crossref","is-referenced-by-count":10,"title":["An algorithm for finding a large independent set in planar graphs"],"prefix":"10.1002","volume":"13","author":[{"given":"Norishige","family":"Chiba","sequence":"first","affiliation":[]},{"given":"Takao","family":"Nishizeki","sequence":"additional","affiliation":[]},{"given":"Nobuji","family":"Saito","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"A. V.Aho J. E.Hopcroft andJ. D.Ullman The Design and Analysis of Computer Algorithms.Addison\u2010Wesley Reading MA (1974)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(76)90071-X"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066439"},{"key":"e_1_2_1_5_2","first-page":"429","article-title":"Every planar map is four colourable, Part I: discharging","volume":"21","author":"Appel K.","year":"1977","journal-title":"Illinois J. Math."},{"key":"e_1_2_1_6_2","article-title":"An approximation algorithm for the maximum independent set problem on planar graphs","author":"Chiba N.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90031-6"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/321850.321852"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230130209","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230130209","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T09:16:49Z","timestamp":1697793409000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230130209"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":7,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["10.1002\/net.3230130209"],"URL":"https:\/\/doi.org\/10.1002\/net.3230130209","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}