On the existence and determination of satisfactory partitions in a graph
Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003), On the existence and determination of satisfactory partitions in a graph, in Ono, Hirotaka, Algorithms and Computation 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings, Springer : Berlin Heidelberg, p. 444-453. 10.1007/978-3-540-24587-2_46
TypeCommunication / Conférence
Book titleAlgorithms and Computation 14th International Symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003, Proceedings
Book authorOno, Hirotaka
MetadataShow full item record
Abstract (EN)The Satisfactory Partition problem consists in deciding if a given graph has a partition of its vertex set into two nonempty sets V 1,V 2 such that for each vertex v, if v ∈ V i then dVi(v) ³ s(v)dVi(v)s(v), where s(v)≤ d(v) is a given integer-valued function. This problem was introduced by Gerber and Kobler [EJOR 125 (2000), 283–291] for s = é\fracd2 ùs=2d. In this paper we study the complexity of this problem for different values of s.
Subjects / Keywordsgraph; NP-complete; degree constraints; Satisfactory partition; complexity; polynomial algorithm
Showing items related by title and author.