By decomposing (i.e., dividing) an interference graph into subgraphs, it becomes feasible to compute close approximations of an optimal channel allocation scheme within a reasonable amount of time. The channel allocation scheme may be used to allocate specific channels to access points (APs) in a wireless, local area network (WLAN).