Pebbling in semi-2-trees

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

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Hurlbert, Glenn
Formato: Articulo
Lenguaje:Inglés
Publicado: 2017
Materias:
Ciencias Exactas
Matemática
pebbling number
k-trees
k-paths
class 0
complexity
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/162382
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-162382
record_format dspace
spelling I19-R120-10915-1623822024-02-06T20:08:18Z http://sedici.unlp.edu.ar/handle/10915/162382 Pebbling in semi-2-trees Alcón, Liliana Graciela Gutiérrez, Marisa Hurlbert, Glenn 2017-07 2024-02-06T17:59:54Z en Ciencias Exactas Matemática pebbling number k-trees k-paths class 0 complexity 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 Πᴾ₂-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. Facultad de Ciencias Exactas Departamento de Matemática Articulo Articulo http://creativecommons.org/licenses/by/4.0/ Creative Commons Attribution 4.0 International (CC BY 4.0) application/pdf 1467-1480
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Exactas
Matemática
pebbling number
k-trees
k-paths
class 0
complexity
spellingShingle Ciencias Exactas
Matemática
pebbling number
k-trees
k-paths
class 0
complexity
Alcón, Liliana Graciela
Gutiérrez, Marisa
Hurlbert, Glenn
Pebbling in semi-2-trees
topic_facet Ciencias Exactas
Matemática
pebbling number
k-trees
k-paths
class 0
complexity
description 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 Πᴾ₂-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.
format Articulo
Articulo
author Alcón, Liliana Graciela
Gutiérrez, Marisa
Hurlbert, Glenn
author_facet Alcón, Liliana Graciela
Gutiérrez, Marisa
Hurlbert, Glenn
author_sort Alcón, Liliana Graciela
title Pebbling in semi-2-trees
title_short Pebbling in semi-2-trees
title_full Pebbling in semi-2-trees
title_fullStr Pebbling in semi-2-trees
title_full_unstemmed Pebbling in semi-2-trees
title_sort pebbling in semi-2-trees
publishDate 2017
url http://sedici.unlp.edu.ar/handle/10915/162382
work_keys_str_mv AT alconlilianagraciela pebblinginsemi2trees
AT gutierrezmarisa pebblinginsemi2trees
AT hurlbertglenn pebblinginsemi2trees
_version_ 1807222362770243584

Ejemplares similares