Details

Autor(en) / Beteiligte

• Bazgan, Cristina
• Tuza, Zsolt
• Vanderpooten, Daniel

Titel

On the Existence and Determination of Satisfactory Partitions in a Graph

Ist Teil von

• Algorithms and Computation, 2003, p.444-453

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• The Satisfactory Partition problem consists in deciding if a given graph has a partition of its vertex set into two nonempty sets V1,V2 such that for each vertex v, if v ∈ Vi then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$d_{V_i}(v) \geq s(v)$\end{document}, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$s = \lceil \frac{d}{2} \rceil$\end{document}. In this paper we study the complexity of this problem for different values of s.