OPTIMAL PATH COVER PROBLEM ON BLOCK GRAPHS AND BIPARTITE PERMUTATION GRAPHS

Authors
SRIKANT R SUNDARAM R SINGH KS RANGAN CP
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
Journal title
Theoretical computer science → ACNP
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.