On Maximum Independent Set of Faces of Triangulated 2-Manifolds
Pablo Diaz‐Gutierrez, M. Gopi · 1974
This algorithm will work only for genus 0 objects. If you have any comments on this document, please do not hesitate to contact the authors. Thank you. We prove bounds and an algorithm to approximate the maximum independent set of faces of a triangulated genus 0 manifold (where two faces are said to be adjacent if they share an edge). This algorithm uses O(|V |) space, and runs in O(|V ||V ′ | + |V ′ | 3) time, where V is the vertex set of the triangulation of the manifold, and V ′ ⊂ V is the set of all odd degree vertices.