An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
From MaRDI portal
Publication:3954831
DOI10.1137/0211055zbMath0492.68051OpenAlexW2042977557MaRDI QIDQ3954831
Nobuji Saito, Norishige Chiba, Takao Nishizeki
Publication date: 1982
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0211055
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems, Optimization and operations research in mitigation of a pandemic, A Simple 2-Approximation for Maximum-Leaf Spanning Tree, Planar orientations with low out-degree and compaction of adjacency matrices, On maximum planar induced subgraphs, An efficient parallel algorithm for computing a large independent set in a planar graph, The maximum clique problem