The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

Maffray, Frédéric; Pastor, Lucas

数学 > 组合数学

arXiv:1602.06817 (math)

[提交于 2016年2月22日 ]

标题：最大权稳定集问题在$(P_6,\mbox{bull})$-free 图中

标题： The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

Authors:Frédéric Maffray, Lucas Pastor

摘要：我们提出一个多项式时间算法，在不包含六顶点诱导路径或一个小牛图（顶点为$a, b, c, d, e$且边为$ab, bc, cd, be, ce$的图）作为诱导子图的图中找到最大权稳定集。

摘要： We present a polynomial-time algorithm that finds a maximum weight stable set in a graph that does not contain as an induced subgraph an induced path on six vertices or a bull (the graph with vertices $a, b, c, d, e$ and edges $ab, bc, cd, be, ce$).

主题：	组合数学 (math.CO) ; 离散数学 (cs.DM)
引用方式：	arXiv:1602.06817 [math.CO]
	(或者 arXiv:1602.06817v1 [math.CO] 对于此版本)
	https://doi.org/10.48550/arXiv.1602.06817

提交历史

来自： Lucas Pastor [查看电子邮件]
[v1] 星期一， 2016 年 2 月 22 日 15:28:00 UTC (32 KB)

全文链接：

获取论文：

查看许可

当前浏览上下文:

math.CO

新的 | 最近的 | 2016-02

切换浏览方式为:

cs
cs.DM
math

参考文献与引用

导出 BibTeX 引用

数学 > 组合数学

标题：最大权稳定集问题在$(P_6,\mbox{bull})$-free 图中

标题： The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

提交历史

获取论文：

参考文献与引用

收藏

文献和引用工具

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

演示

推荐器和搜索工具

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

数学 > 组合数学

标题： 最大权稳定集问题在$(P_6,\mbox{bull})$-free 图中 显示英文标题

标题： The maximum weight stable set problem in $(P_6,\mbox{bull})$-free graphs

提交历史

获取论文：

参考文献与引用

BibTeX 格式的引用

收藏

文献和引用工具

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

演示

推荐器和搜索工具

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

标题：最大权稳定集问题在$(P_6,\mbox{bull})$-free 图中