Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs
Domination and its variations arise in many applications, in particular in those involving strategic placement of items at vertices of a network. For general graphs these problems are NP-hard, however, domination in graphs has been shown to be polynomially solvable in several graph classes. In this...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Objeto de conferencia Resumen |
| Lenguaje: | Inglés |
| Publicado: |
2013
|
| Materias: | |
| Acceso en línea: | http://sedici.unlp.edu.ar/handle/10915/94544 |
| Aporte de: |
| id |
I19-R120-10915-94544 |
|---|---|
| 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 K-domination in graphs NP-hard Graphs |
| spellingShingle |
Ciencias Informáticas K-domination in graphs NP-hard Graphs Argiroffo, G. Escalante, M. Ugarte, M. E. Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| topic_facet |
Ciencias Informáticas K-domination in graphs NP-hard Graphs |
| description |
Domination and its variations arise in many applications, in particular in those involving strategic placement of items at vertices of a network. For general graphs these problems are NP-hard, however, domination in graphs has been shown to be polynomially solvable in several graph classes. In this work we consider a generalization of this problem called k-domination in graphs. |
| format |
Objeto de conferencia Resumen |
| author |
Argiroffo, G. Escalante, M. Ugarte, M. E. |
| author_facet |
Argiroffo, G. Escalante, M. Ugarte, M. E. |
| author_sort |
Argiroffo, G. |
| title |
Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| title_short |
Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| title_full |
Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| title_fullStr |
Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| title_full_unstemmed |
Polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| title_sort |
polyhedral study of the 2-dominating set polytope of cycles and cactus graphs |
| publishDate |
2013 |
| url |
http://sedici.unlp.edu.ar/handle/10915/94544 |
| work_keys_str_mv |
AT argiroffog polyhedralstudyofthe2dominatingsetpolytopeofcyclesandcactusgraphs AT escalantem polyhedralstudyofthe2dominatingsetpolytopeofcyclesandcactusgraphs AT ugarteme polyhedralstudyofthe2dominatingsetpolytopeofcyclesandcactusgraphs |
| bdutipo_str |
Repositorios |
| _version_ |
1764820491541938179 |