• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Satisfactory graph partition, variants, and generalizations

Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2010), Satisfactory graph partition, variants, and generalizations, European Journal of Operational Research, 206, 2, p. 271-280. http://dx.doi.org/10.1016/j.ejor.2009.10.019

Type
Article accepté pour publication ou publié
Date
2010
Journal name
European Journal of Operational Research
Volume
206
Number
2
Pages
271-280
Publication identifier
http://dx.doi.org/10.1016/j.ejor.2009.10.019
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Tuza, Zsolt
Vanderpooten, Daniel
Abstract (EN)
The Satisfactory Partition problem asks for deciding if a given graph has a partition of its vertex set into two nonempty parts such that each vertex has at least as many neighbors in its part as in the other part. This problem was introduced by Gerber and Kobler [M. Gerber, D. Kobler, Algorithmic approach to the satisfactory graph partitioning problem, European Journal of Operational Research 125 (2000) 283–291] and studied further by other authors. In this paper we first review some applications and related problems. Then, we survey structural, complexity, and approximation results obtained for Satisfactory Partition and for some of its variants and generalizations. A list of open questions concludes this survey.
Subjects / Keywords
Degree constraints; Approximation algorithm; Vertex partition; Combinatorial optimization; Complexity theory

Related items

Showing items related by title and author.

  • Thumbnail
    On the existence and determination of satisfactory partitions in a graph 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) Communication / Conférence
  • Thumbnail
    Complexity and approximation of satisfactory partition problems 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2005) Communication / Conférence
  • Thumbnail
    Complexity of the satisfactory partition problem 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2003) Document de travail / Working paper
  • Thumbnail
    The satisfactory partition problem 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2006) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of satisfactory bisection problems 
    Bazgan, Cristina; Tuza, Zsolt; Vanderpooten, Daniel (2008) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo