Artículo
Pebbling in semi-2-trees
Fecha de publicación:
07/2017
Editorial:
Elsevier Science
Revista:
Discrete Mathematics
ISSN:
0012-365X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
Graph pebbling is a network model for transporting discrete resources that are consumed in transit. Deciding whether a given configuration on a particular graph can reach a specified target is NP-complete, even for diameter two graphs, and deciding whether the pebbling number has a prescribed upper bound is Π2 P-complete. Recently we proved that the pebbling number of a split graph can be computed in polynomial time. This paper advances the program of finding other polynomial classes, moving away from the large tree width, small diameter case (such as split graphs) to small tree width, large diameter, continuing an investigation on the important subfamily of chordal graphs called k-trees. In particular, we provide a formula, that can be calculated in polynomial time, for the pebbling number of any semi-2-tree, falling shy of the result for the full class of 2-trees.
Palabras clave:
Class 0
,
Complexity
,
K-Paths
,
K-Trees
,
Pebbling Number
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(CCT - LA PLATA)
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Articulos de CTRO.CIENTIFICO TECNOL.CONICET - LA PLATA
Citación
Alcón, Liliana Graciela; Gutierrez, Marisa; Hulbert, Glenn; Pebbling in semi-2-trees; Elsevier Science; Discrete Mathematics; 340; 7; 7-2017; 1467-1480
Compartir
Altmétricas