• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537~n)
【24h】

Maximum Independent Set in Graphs of Average Degree at Most Three in O(1.08537~n)

机译：O（1.08537〜n）中平均度最多为3的图中的最大独立集

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We show that MAXIMUM INDEPENDENT Set on connected graphs of average degree at most three can be solved in 0(1.08537~n) time and linear space. This improves previous results on graphs of maximum degree three, as our connectivity requirement only functions to ensure that each connected component has average degree at most three. We link this result to exact algorithms of Maximum Independent Set on general graphs. Also, we obtain a faster parameterised algorithm for Vertex Cover restricted to graphs of maximum degree three running in time O~*(1.1781~k).
机译：结果表明，在0（1.08537〜n）的时间和线性空间中，最多可以求解3个平均度的连通图上的MAXINDUM INDEPENDENT。这改善了先前在最大三度图中的结果，因为我们的连接要求仅用于确保每个连接的组件最多具有三个平均度。我们将此结果链接到一般图上的最大独立集的精确算法。此外，我们获得了一种针对顶点覆盖的更快的参数化算法，该算法限于时间为O〜*（1.1781〜k）的最大三度图。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号