| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428287 | Information Processing Letters | 2006 | 4 Pages |
Abstract
We give a linear time 4/3-approximation algorithm for the problem of finding the maximum number of vertex-disjoint paths of order 3 in subcubic graphs without pendant vertices, which improves previously known results [K. Kawarabayashi, H. Matsuda, Y. Oda, K. Ota, Path factors in cubic graphs, Journal of Graph Theory 39 (2002) 188–193; A. Kelmans, D. Mubayi, How many disjoint 2-edge paths must a cubic graph have?, Journal of Graph Theory 45 (2004) 57–79].
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
