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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Argiroffo, Gabriela
Formato: Objeto de conferencia
Lenguaje:Inglés
Publicado: 2013
Materias:
Ciencias Informáticas
2-domination
Facet
Tree
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/94585
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
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

Ejemplares similares