Article ID Journal Published Year Pages File Type
429285 Information Processing Letters 2006 6 Pages PDF
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