On the Existence and Determination of Satisfactory Partitions in a Graph
On the Existence and Determination of Satisfactory Partitions in a Graph
复制标题
DOI：
10.1007/978-3-540-24587-2_46
复制
发表时间：
2003-12
期刊：
影响因子：
--
通讯作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
中科院分区：
文献类型：
--
作者：
C. Bazgan;Z. Tuza;D. Vanderpooten
满足性划分问题在于确定一个给定的图是否将其顶点集划分成两个非空集V1，V2，使得对于每个顶点v，IFv∈Viten，其中(V)≤d(V)是给定的整值函数。这个问题是由Gerber和Kobler[EJOR125(2000)，283-291]提出的。在这篇文章中，我们研究了这个问题对于不同的值的复杂性。
TheSatisfactory Partitionproblem consists in deciding if a given graph has a partition of its vertex set into two nonempty setsV1,V2such that for each vertexv, ifv∈Vithen, wheres(v)≤d(v) is a given integer-valued function. This problem was introduced by Gerber and Kobler [EJOR125 (2000), 283–291] for. In this paper we study the complexity of this problem for different values ofs.