On the dominating set polytope
Bouchakour, Mustapha; Contenza, Teresa; Lee, C.W; Mahjoub, Ali Ridha (2008), On the dominating set polytope, European Journal of Combinatorics, 29, 3, p. 652-661. http://dx.doi.org/10.1016/j.ejc.2007.03.010
Type
Article accepté pour publication ou publiéDate
2008Journal name
European Journal of CombinatoricsVolume
29Number
3Publisher
Elsevier
Pages
652-661
Publication identifier
Metadata
Show full item recordAbstract (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.Subjects / Keywords
PolytopeRelated items
Showing items related by title and author.
-
Bouchakour, Mustapha; Mahjoub, Ali Ridha (1997) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Mailfert, Jean (2006) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Kerivin, Hervé; Didi Biha, Mohamed (2008) Article accepté pour publication ou publié
-
Mahjoub, Ali Ridha; Nocq, Charles (1999) Article accepté pour publication ou publié
-
Aoudia, Lamia; Nguyen, Viet Hung; Mahjoub, Ali Ridha; Aider, Meziane (2014-11) Communication / Conférence