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.

Detalles Bibliográficos
Autores principales: Song, Yinglei, Yu, Menghong
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Public Library of Science 2015
Materias:
Research Article
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
_version_ 1782365398432219136
author Song, Yinglei
Yu, Menghong
author_facet Song, Yinglei
Yu, Menghong
author_sort Song, Yinglei
collection PubMed
description 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.
format Online
Article
Text
id pubmed-4388525
institution National Center for Biotechnology Information
language English
publishDate 2015
publisher Public Library of Science
record_format MEDLINE/PubMed
spelling pubmed-43885252015-04-21 On the Treewidths of Graphs of Bounded Degree Song, Yinglei Yu, Menghong PLoS One Research Article 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. Public Library of Science 2015-04-07 /pmc/articles/PMC4388525/ /pubmed/25849278 http://dx.doi.org/10.1371/journal.pone.0120880 Text en © 2015 Song, Yu http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
spellingShingle Research Article
Song, Yinglei
Yu, Menghong
On the Treewidths of Graphs of Bounded Degree
title On the Treewidths of Graphs of Bounded Degree
title_full On the Treewidths of Graphs of Bounded Degree
title_fullStr On the Treewidths of Graphs of Bounded Degree
title_full_unstemmed On the Treewidths of Graphs of Bounded Degree
title_short On the Treewidths of Graphs of Bounded Degree
title_sort on the treewidths of graphs of bounded degree
topic Research Article
url 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
work_keys_str_mv AT songyinglei onthetreewidthsofgraphsofboundeddegree
AT yumenghong onthetreewidthsofgraphsofboundeddegree

Ejemplares similares