An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs.

Norishige Chiba Takao Nishizeki Nobuji Saito

Published in: SIAM J. Comput. (1982)

Keyphrases

dynamic programming
planar graphs
worst case
expectation maximization
computational complexity
np hard
undirected graph
objective function
optimal solution
search space
probabilistic model
closed form