Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429285 | Information Processing Letters | 2006 | 6 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics