Cargando…
On the Treewidths of Graphs of Bounded Degree
In this paper, we develop a new technique to study the treewidth of graphs with bounded degree. We show that the treewidth of a graph G = (V, E) with maximum vertex degree d is at most [Formula: see text] for sufficiently large d, where C is a constant.
| Autores principales: | , |
|---|---|
| Formato: | Online Artículo Texto |
| Lenguaje: | English |
| Publicado: |
Public Library of Science
2015
|
| Materias: | |
| Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4388525/ https://www.ncbi.nlm.nih.gov/pubmed/25849278 http://dx.doi.org/10.1371/journal.pone.0120880 |