On the k-path partition of graphs |
| |
Authors: | George Steiner |
| |
Affiliation: | Management Science and Information Systems Area, McMaster University, 1280 Main Street West, L8S 4K1, Hamilton, Ont., Canada |
| |
Abstract: | The k-path partition problem is to partition a graph into the minimum number of paths, so that none of them has length more than k, for a given positive integer k. The problem is a generalization of the Hamiltonian path problem and the problem of partitioning a graph into the minimum number of paths. The k-path partition problem remains NP-complete on the class of chordal bipartite graphs if k is part of the input, and we show that it is NP-complete on the class of comparability graphs even for k=3. On the positive side, we present a polynomial-time solution for the problem, with any k, on bipartite permutation graphs, which form a subclass of chordal bipartite graphs. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|