无长爪稀疏图的最大权独立集

《ACM Transactions on Algorithms》:Max Weight Independent Set in sparse graphs with no long claws

【字体: 大 中 小 】 时间:2026年09月21日 来源:ACM Transactions on Algorithms 1.4

编辑推荐:

   摘要AI 摘要要查看此AI生成的摘要,您必须拥有高级访问权限。了解更多登录摘要摘要对于图 $G$ 和 $H$,我们说 $G$ 是 $H$-自由的,如果它不包含 $H$ 作为诱导子图。早在20世纪80年代初,Alekseev 就观察到,除非 $H$ 的每个连通分量都是路径或细分

  

摘要

摘要

对于图 $G$ 和 $H$,我们说 $G$ 是 $H$-自由的,如果它不包含 $H$ 作为诱导子图。早在20世纪80年代初,Alekseev 就观察到,除非 $H$ 的每个连通分量都是路径或细分爪(即通过将三叶星图的每条边细分若干次(可能为零次)而得到的图),否则最大权独立集问题(MWIS)在 $H$-自由图中仍然是 NP-难的。自那时以来,确定 MWIS 在剩余这些情况下的复杂度一直是算法图论中最重要的问题之一。
在本文中,我们通过为排除固定图路径森林和细分爪作为诱导子图、以及排除固定二部完全图作为子图的图提供 MWIS 的多项式时间算法,朝着解决这一问题迈出了重要一步。

AI 摘要

AI生成的摘要(实验性)

本摘要由自动化工具生成,未经本文作者撰写或审核。它旨在支持文献检索,帮助读者评估相关性,并协助来自相邻研究领域的读者理解该工作。它旨在补充作者提供的摘要,后者仍然是论文的主要摘要。完整文章仍然是具有权威性的正式版本。点击此处了解更多。

点击此处评论此摘要的准确性、清晰度和有用性。这样做将有助于改进并生成未来的版本。

要查看此AI生成的通俗摘要,您必须拥有高级访问权限。

相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号