On the k-path cover problem for cacti |
| |
Authors: | Zemin Jin Xueliang Li |
| |
Affiliation: | 1. Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, PR China;2. Department of Mathematics, Zhejiang Normal University, Jinhua 321004, PR China |
| |
Abstract: | In this paper we investigate the k-path cover problem for graphs, which is to find the minimum number of vertex disjoint k-paths that cover all the vertices of a graph. The k-path cover problem for general graphs is NP-complete. Though notable applications of this problem to database design, network, VLSI design, ring protocols, and code optimization, efficient algorithms are known for only few special classes of graphs. In order to solve this problem for cacti, i.e., graphs where no edge lies on more than one cycle, we introduce the so-called Steiner version of the k-path cover problem, and develop an efficient algorithm for the Steiner k-path cover problem for cacti, which finds an optimal k-path cover for a given cactus in polynomial time. |
| |
Keywords: | 68R10 05C70 05C85 90C27 68Q17 94C15 |
本文献已被 ScienceDirect 等数据库收录! |
|