OPTIMAL PATH COVER PROBLEM ON BLOCK GRAPHS AND BIPARTITE PERMUTATION GRAPHS

Citation
R. Srikant et al., OPTIMAL PATH COVER PROBLEM ON BLOCK GRAPHS AND BIPARTITE PERMUTATION GRAPHS, Theoretical computer science, 115(2), 1993, pp. 351-357
Citations number
9
Categorie Soggetti
Computer Sciences","Computer Applications & Cybernetics",Mathematics
ISSN journal
03043975
Volume
115
Issue
2
Year of publication
1993
Pages
351 - 357
Database
ISI
SICI code
0304-3975(1993)115:2<351:OPCPOB>2.0.ZU;2-Q
Abstract
The optimal path cover problem is to find a minimum number of vertex d isjoint paths which together cover all the vertices of the graph. In t his paper, we present linear-time algorithms for the optimal path cove r problem for the class of block graphs and bipartite permutation grap hs.