|
|||||
|
|
A 3-approximation for the pathwidth of Halin graphs |
|
| Authors: | Fedor V. Fomin Dimitrios M. Thilikos |
| Affiliation: | aDepartment of Informatics, University of Bergen N-5020, Bergen, Norway bDepartament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, E-08034, Barcelona, Spain |
| Abstract: | We prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton. |
| Keywords: | Halin graph Pathwidth Linear width |
| 本文献已被 ScienceDirect 等数据库收录！ | |