• français
    • English
  • français 
    • 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 independent dominating set polytope

Thumbnail
Date
2006
Dewey
Recherche opérationnelle
Sujet
Polynomial time separation algorithm; Graph; Polytope
Journal issue
European Journal of Combinatorics
Volume
27
Number
4
Publication date
05-2006
Article pages
601-616
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejc.2004.07.015
URI
https://basepub.dauphine.fr/handle/123456789/3694
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Mahjoub, Ali Ridha
Mailfert, Jean
Type
Article accepté pour publication ou publié
Abstract (EN)
In this paper, we consider the independent dominating set polytope. We give a complete linear description of that polytope when the graph is reduced to a cycle. This description uses a general class of valid inequalities introduced in [T.M. Contenza, Some results on the dominating set polytope, Ph.D. Dissertation, University of Kentucky, 2000]. We devise a polynomial time separation algorithm for these inequalities. As a consequence, we obtain a polynomial time cutting plane algorithm for the minimum (maximum) independent dominating set problem on a cycle. We also introduce a lifting operation called twin operation, and discuss some polyhedral consequences. In particular, we show that the above results can be extended to a more general class of 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.