|
|||||
|
|
Pathwidth of cubic graphs and exact algorithms |
|
| Authors: | Fedor V. Fomin,Kjartan Hø ie |
| Affiliation: | Department of Informatics, University of Bergen N-5020, Bergen, Norway |
| Abstract: | We prove that for any ?>0 there exists an integer n? such that the pathwidth of every cubic (or 3-regular) graph on n>n? vertices is at most (1/6+?)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three. |
| Keywords: | Treewidth Pathwidth Cubic graph Exact exponential algorithm Maximum independent set Max-cut Minimum dominating set Graph algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ | |