New facets of the 2-dominating set polytope of trees
Given a graph G and a nonnegative integer number k, a k- dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural g...
| Autor principal: | |
|---|---|
| Formato: | Objeto de conferencia |
| Lenguaje: | Inglés |
| Publicado: |
2013
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/94585 |
| Aporte de: |
| id |
I19-R120-10915-94585 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de La Plata |
| institution_str |
I-19 |
| repository_str |
R-120 |
| collection |
SEDICI (UNLP) |
| language |
Inglés |
| topic |
Ciencias Informáticas 2-domination Facet Tree |
| spellingShingle |
Ciencias Informáticas 2-domination Facet Tree Argiroffo, Gabriela New facets of the 2-dominating set polytope of trees |
| topic_facet |
Ciencias Informáticas 2-domination Facet Tree |
| description |
Given a graph G and a nonnegative integer number k, a k- dominating set in G is a subset of vertices D such that every vertex in the graph is adjacent to at least k elements of D. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G. This is a natural generalization of the well-known dominating set polytope in graphs. In this work we study the 2-dominating set polytope of trees and we will provide new facet de ning inequalities for it. |
| format |
Objeto de conferencia Objeto de conferencia |
| author |
Argiroffo, Gabriela |
| author_facet |
Argiroffo, Gabriela |
| author_sort |
Argiroffo, Gabriela |
| title |
New facets of the 2-dominating set polytope of trees |
| title_short |
New facets of the 2-dominating set polytope of trees |
| title_full |
New facets of the 2-dominating set polytope of trees |
| title_fullStr |
New facets of the 2-dominating set polytope of trees |
| title_full_unstemmed |
New facets of the 2-dominating set polytope of trees |
| title_sort |
new facets of the 2-dominating set polytope of trees |
| publishDate |
2013 |
| url |
http://sedici.unlp.edu.ar/handle/10915/94585 |
| work_keys_str_mv |
AT argiroffogabriela newfacetsofthe2dominatingsetpolytopeoftrees |
| bdutipo_str |
Repositorios |
| _version_ |
1764820491638407169 |