无向圆盘图中最大r跳独立邻居数的估计

作者：周志诚; 李翠静

来源：软件, 2016, 37(11): 23-29.

• 最大r跳
• 无向圆盘图
• 极大独立集
• 连通控制集

本文考虑无向圆盘图中的最大r-跳独立邻居数(r≥2)。给定一个圆盘图G=(V,E),对任意v?V,用N’(V)表示所有距节点v跳数最多为r的节点集合,则对G中任何一个r-跳独立集I,其在N’(V)内最多有β个节点,■这里K是圆盘图的最大圆盘半径与最小圆盘半径的比值.

• 单位
  北京邮电大学