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

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

On the independent dominating set polytope

Thumbnail
Date
2006
Indexation documentaire
Recherche opérationnelle
Subject
Polynomial time separation algorithm; Graph; Polytope
Nom de la revue
European Journal of Combinatorics
Volume
27
Numéro
4
Date de publication
05-2006
Pages article
601-616
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejc.2004.07.015
URI
https://basepub.dauphine.fr/handle/123456789/3694
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Mahjoub, Ali Ridha
Mailfert, Jean
Type
Article accepté pour publication ou publié
Résumé en anglais
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

 Cette création est mise à disposition sous un contrat Creative Commons.