Portal de Periódicos da CAPES

Parallel Approximation Schemes for problems on planar graphs

1996; Springer Science+Business Media; Volume: 33; Issue: 4 Linguagem: Inglês

10.1007/s002360050049

1432-0525

Josep Dı́az, Marı́a Serna, Jacobo Torán,

Computational Geometry and Mesh Generation

This paper describes a technique to obtain NC Approximations Schemes for the Maximum Independent Set in planar graphs and related optimization problems. The strategy consists in decomposing the graph into K-outerplanar subgraphs and solve for each K-outerplanar using tree contraction techniques.