The Generalized Stable Set Problem for Claw-Free Bidirected Graphs
The Generalized Stable Set Problem for Claw-Free Bidirected Graphs
复制标题
无爪双向图的广义稳定集问题
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
A. Tamura
中科院分区：
文献类型：
--
作者：
D. Nakamura;A. Tamura
双向图是无向图的推广。广义稳定集问题是无向图的最大权稳定集问题到双向图的推广。已知后一个问题对于无爪无向图是多项式可解的。在本文中，我们定义了无爪双向图，并证明了无爪双向图的广义稳定集问题也是多项式可解的。
Bidirected graphs are a generalization of undirected graphs. The generalized stable set problem is an extension of the maximum weight stable set problem for undirected graphs to bidirected graphs. It is known that the latter problem is polynomially solvable for claw-free undirected graphs. In this paper, we define claw-free bidirected graphs and show that the generalized stable set problem is also polynomially solvable for claw-free bidirected graphs.