• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the dominating set polytope

Thumbnail
Date
2008
Dewey
Probabilités et mathématiques appliquées
Sujet
Polytope
Journal issue
European Journal of Combinatorics
Volume
29
Number
3
Publication date
2008
Article pages
652-661
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejc.2007.03.010
URI
https://basepub.dauphine.fr/handle/123456789/2122
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bouchakour, Mustapha
Contenza, Teresa
Lee, C.W
Mahjoub, Ali Ridha
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper, we study the dominating set polytope in the class of graphs that decompose by one-node cutsets where the pieces are cycles. We describe some classes of facets and procedures to construct facets of the polytope in that class of graphs, and establish some structural properties. As a consequence we obtain a complete description of the polytope by a system of inequalities when the graph is a cycle. We also show that the separation problem related to that system can be solved in polynomial time. This yields a polynomial time cutting plane algorithm for the minimum weight dominating set problem in that case. We further discuss the applications for the class of cactus graphs.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.