Bounded-degree independent sets in planar graphs

被引：2
作者：
Biedl, T [1 ]
Wilkinson, DF [1 ]
机构：
[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada
来源：
THEORY OF COMPUTING SYSTEMS | 2005年 / 38卷 / 03期
关键词：
D O I：
10.1007/s00224-005-1139-0
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
An independent set of a graph is a set of vertices without edges between them. Every planar graph has an independent set of size at least 1/4n and there are planar graphs for which any independent set has size at most 1/4n. In this paper similar bounds are provided for the problem of bounded-degree independent set, i.e., an independent set where additionally all vertices have degree less than a pre-specified bound D. Our upper and lower bounds match (up to a small constant) for D <= 16.
引用
收藏
页码：253 / 278
页数：26
相关论文
共 12 条
12