Skip to main content
CenXiv.org
此网站处于试运行阶段,支持我们!
我们衷心感谢所有贡献者的支持。
贡献
赞助
cenxiv logo > cs > arXiv:2507.00235v2

帮助 | 高级搜索

计算机科学 > 计算几何

arXiv:2507.00235v2 (cs)
[提交于 2025年6月30日 (v1) ,最后修订 2025年7月2日 (此版本, v2)]

标题: 某些图类上的最小选择子集

标题: Minimum Selective Subset on Some Graph Classes

Authors:Bubai Manna
摘要: 在一个连通的简单图 G = (V(G),E(G)) 中,每个顶点都从颜色集合 C={1, 2,..., c}中分配一种颜色。 顶点集 V(G) 被划分为 V_1, V_2, ... ,V_c,其中所有在 V_j 中的顶点都具有相同的颜色 j。 V(G) 的一个子集 S 被称为选择子集,如果对于 V(G) 中的每个顶点 v,如果 v 在 V_j 中,则在 (S union (V(G) V_j)) 中至少有一个最近邻与 v 具有相同颜色。 最小选择子集(MSS)问题旨在找到一个最小大小的选择子集。 该问题最早由 Wilfong 于 1991 年在欧几里得平面上的一组点中提出,其中提出了两个主要问题,MCS(最小一致子集)和 MSS。 在图算法中,唯一已知的结果是 MSS 问题是 NP 完全的,如 2018 年所示。 除此之外,到目前为止没有进一步的进展。 相比之下,MCS 问题多年来在各种图类中得到了广泛研究。 因此,在这项工作中,我们还扩展了在各种图类上 MSS 的算法研究。 我们首先为具有 n 个顶点且不管颜色数量如何的一般图提供了一个 log(n)-近似算法。 我们还表明,当仅限于两种颜色时,该问题在平面图中仍然保持 NP 完全。 最后,我们提供了在树和单位区间图上计算任意数量颜色下的最优解的多项式时间算法。
摘要: In a connected simple graph G = (V(G),E(G)), each vertex is assigned a color from the set of colors C={1, 2,..., c}. The set of vertices V(G) is partitioned as V_1, V_2, ... ,V_c, where all vertices in V_j share the same color j. A subset S of V(G) is called Selective Subset if, for every vertex v in V(G), and if v is in V_j, at least one of its nearest neighbors in (S union (V(G)\ V_j)) has the same color as v. The Minimum Selective Subset (MSS) problem seeks to find a selective subset of minimum size. The problem was first introduced by Wilfong in 1991 for a set of points in the Euclidean plane, where two major problems, MCS (Minimum Consistent Subset) and MSS, were proposed. In graph algorithms, the only known result is that the MSS problem is NP-complete, as shown in 2018. Beyond this, no further progress has been made to date. In contrast, the MCS problem has been widely studied in various graph classes over the years. Therefore, in this work, we also extend the algorithmic study of MSS on various graph classes. We first present a log(n)-approximation algorithm for general graphs with n vertices and regardless of the number of colors. We also show that the problem remains NP-complete in planar graphs when restricted to just two colors.. Finally, we provide polynomial-time algorithms for computing optimal solutions in trees and unit interval graphs for any number of colors.
评论: 这项工作已被接受于CCCG 2025
主题: 计算几何 (cs.CG) ; 计算复杂性 (cs.CC)
引用方式: arXiv:2507.00235 [cs.CG]
  (或者 arXiv:2507.00235v2 [cs.CG] 对于此版本)
  https://doi.org/10.48550/arXiv.2507.00235
通过 DataCite 发表的 arXiv DOI

提交历史

来自: Bubai Manna [查看电子邮件]
[v1] 星期一, 2025 年 6 月 30 日 20:04:56 UTC (1,025 KB)
[v2] 星期三, 2025 年 7 月 2 日 06:03:49 UTC (194 KB)
全文链接:

获取论文:

    查看标题为《》的 PDF
  • 查看中文 PDF
  • 查看 PDF
  • HTML(实验性)
  • TeX 源代码
  • 其他格式
查看许可
当前浏览上下文:
cs.CG
< 上一篇   |   下一篇 >
新的 | 最近的 | 2025-07
切换浏览方式为:
cs
cs.CC

参考文献与引用

  • NASA ADS
  • 谷歌学术搜索
  • 语义学者
a 导出 BibTeX 引用 加载中...

BibTeX 格式的引用

×
数据由提供:

收藏

BibSonomy logo Reddit logo

文献和引用工具

文献资源探索 (什么是资源探索?)
连接的论文 (什么是连接的论文?)
Litmaps (什么是 Litmaps?)
scite 智能引用 (什么是智能引用?)

与本文相关的代码,数据和媒体

alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)

演示

复制 (什么是复制?)
Hugging Face Spaces (什么是 Spaces?)
TXYZ.AI (什么是 TXYZ.AI?)

推荐器和搜索工具

影响之花 (什么是影响之花?)
核心推荐器 (什么是核心?)
IArxiv 推荐器 (什么是 IArxiv?)
  • 作者
  • 地点
  • 机构
  • 主题

arXivLabs:与社区合作伙伴的实验项目

arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。

与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。

有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.

这篇论文的哪些作者是支持者? | 禁用 MathJax (什么是 MathJax?)
  • 关于
  • 帮助
  • contact arXivClick here to contact arXiv 联系
  • 订阅 arXiv 邮件列表点击这里订阅 订阅
  • 版权
  • 隐私政策
  • 网络无障碍帮助
  • arXiv 运营状态
    通过...获取状态通知 email 或者 slack

京ICP备2025123034号