Browsing by Author "Pan, JJ"

Now showing 1 - 2 of 2

Isometric-path numbers of block graphs
(2005-01-31)
Pan, JJ
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
An isometric path between two vertices in a graph G is a shortest path joining them. The isometric-path number of G, denoted by ip(G), is the minimum number of isometric paths required to cover all vertices of G. In this paper, we determine exact values of isometric-path numbers of block graphs. We also give a linear-time algorithm for finding the corresponding paths. (C) 2004 Elsevier B.V. All rights reserved.
Path partition for graphs with special blocks
(2005-01-30)
Pan, JJ
;
Chang, GJ
;
應用數學系
;
Department of Applied Mathematics
The path-partition problem is to find a minimum number of vertex-disjoint paths that cover all vertices of a given graph. This paper studies the path-partition problem from an algorithmic point of view. As the Hamiltonian path problem is NP-complete for many classes of graphs, so is the path-partition problem. The main result of this paper is to present a linear-time algorithm for the path-partition problem in graphs whose blocks are complete graphs, cycles or complete bipartite graphs. (C) 2004 Elsevier B.V. All rights reserved.