A study of graph width parameters

本研究的目的是考虑其对偶性，设计树宽度、分支宽度、带宽、路径宽度等的近似算法。研究结果表明，无at图的距离路径宽度可以在多项式时间内近似为常数因子。此外，考虑到图的对偶性，给出了图的笛卡尔积的树宽下界，并将路径宽度禁制结构的概念推广到拟阵。

The purpose of this study is to design approximation algorithms for tree-width, branch-width, bandwidth, path-width, and so on by considering its duality. As the result of the study, we showed that the distance path width of AT-free graphs can be approximated within a constant factor in polynomial time. Moreover, by considering the duality, we gave lower bounds for tree-width for Cartesian products of graphs, and extended the notion of forbidden structure for path-width to matroids.