Abstract
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 \(d_{V_i}(v) \geq 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 = \lceil \frac{d}{2} \rceil\). In this paper we study the complexity of this problem for different values of s.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodlaender, H.L.: On disjoint cycles. International Journal of Foundations of Computer Science 5(1), 59–68 (1994)
Chvátal, V.: Recognizing decomposable graphs. Journal of Graph Theory 8, 51–53 (1984)
Gerber, M., Kobler, D.: Algorithmic approach to the satisfactory graph partitioning problem. European Journal of Operation Research 125, 283–291 (2000)
Lovász, L.: Coverings and coloring of hypergraphs. In: Proceedings of 4th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, pp. 3–12 (1973)
Stiebitz, M.: Decomposing graphs under degree constraints. Journal of Graph Theory 23, 321–324 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bazgan, C., Tuza, Z., Vanderpooten, D. (2003). On the Existence and Determination of Satisfactory Partitions in a Graph. In: Ibaraki, T., Katoh, N., Ono, H. (eds) Algorithms and Computation. ISAAC 2003. Lecture Notes in Computer Science, vol 2906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24587-2_46
Download citation
DOI: https://doi.org/10.1007/978-3-540-24587-2_46
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20695-8
Online ISBN: 978-3-540-24587-2
eBook Packages: Springer Book Archive