计算机科学 > 计算几何
[提交于 2025年6月30日
(v1)
,最后修订 2025年7月2日 (此版本, v2)]
标题: 某些图类上的最小选择子集
标题: Minimum Selective Subset on Some Graph Classes
摘要: 在一个连通的简单图 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 完全。 最后,我们提供了在树和单位区间图上计算任意数量颜色下的最优解的多项式时间算法。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.