The path-partition problem in bipartite distance-hereditary graphs

Hong Gwa Yeh, Gerard J. Chang

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

A path partition of a graph is a collection of vertex-disjoint paths that cover all vertices of the graph. The path-partition problem is to find a path partition of minimum size. This paper gives a linear-time algorithm for the path-partition problem in bipartite distance-hereditary graphs.

Original languageEnglish
Pages (from-to)353-360
Number of pages8
JournalTaiwanese Journal of Mathematics
Volume2
Issue number3
DOIs
StatePublished - Sep 1998

Keywords

  • Distance-hereditary graph
  • Hamiltonian path
  • Path partition

Fingerprint

Dive into the research topics of 'The path-partition problem in bipartite distance-hereditary graphs'. Together they form a unique fingerprint.

Cite this