I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone here can help me find one.
Thanks in advance.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
I haven't got any paper, but looking through my favorite book regarding approximation algorithms i've got something.
It is named: The Design of Approximation Algorithms. You find it free for download (even legal) on https://www.designofapproxalgs.com.
Take a look at page 269 (ff.) especially page 271 should be interesting for you as they describe and proof a PTAS for max independent set in planar graphs.
It might not be "front of the line" research or results but hope it helps.
