Treewidth , partial k-trees , and chordal graphs
Treewidth , partial k-trees , and chordal graphs
复制标题
树宽、部分 k 树和弦图
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
P. Heggernes
中科院分区：
文献类型：
--
作者：
P. Heggernes
如果输入图具有有界树宽或属于受限图类，则许多在一般图上为 NP 困难的图问题具有多项式时间解。在本文档中，我们回顾了一些处理图问题的 NP 困难的技术。特别是，我们解释了图参数树宽和路径宽度，并给出了小树宽和路径宽度图的多项式时间算法的示例。此外，我们研究了弦图类和弦图的几个子类，因为许多难题在这些类上可以多项式求解。此外，还提到并解释了一些重要且有用的图论概念。
Many graph problems that are NP-hard on general graphs, have polynomial time solutions if the input graph has bounded treewidth or if it belongs to a restricted graph class. In this document, we review some of the techniques for coping with NP-hardness of graph problems. In particular, we explain graph parameters treewidth and pathwidth, and give examples of polynomial time algorithms for graphs of small treewidth and pathwidth. Furthermore, we study the class of chordal graphs and several subclasses of chordal graphs, since many hard problems are polynomially solvable on these classes. In addition, some important and useful graph theoretical notions are mentioned and explained.