Approximation algorithms for finding and partitioning unit-disk graphs into co-k-plexes |
| |
Authors: | Balabhaskar Balasundaram Shyam Sundar Chandramouli Svyatoslav Trukhanov |
| |
Affiliation: | (3) Department of Industrial & Systems Engineering, Texas A&M University College Station, Texas, USA; |
| |
Abstract: | This article studies a degree-bounded generalization of independent sets called co-k-plexes. Constant factor approximation algorithms are developed for the maximum co-k-plex problem on unit-disk graphs. The related problem of minimum co-k-plex coloring that generalizes classical vertex coloring is also studied in the context of unit-disk graphs. We extend several classical approximation results for independent sets in UDGs to co-k-plexes, and settle a recent conjecture on the approximability of co-k-plex coloring in UDGs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |