Optimal path cover problem on block graphs and bipartite permutation graphs

R. Srikant, Ravi Sundaram, Karan Sher Singh, C. Pandu Rangan

Research output: Contribution to journalArticle

Abstract

The optimal path cover problem is to find a minimum number of vertex disjoint paths which together cover all the vertices of the graph. In this paper, we present linear-time algorithms for the optimal path cover problem for the class of block graphs and bipartite permutation graphs.

Original languageEnglish (US)
Pages (from-to)351-357
Number of pages7
JournalTheoretical Computer Science
Volume115
Issue number2
DOIs
StatePublished - Jul 19 1993
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal path cover problem on block graphs and bipartite permutation graphs'. Together they form a unique fingerprint.

Cite this