Minimum Height Path Partitioning of Trees

Bagheri, A.; Razzazi, M.

Minimum Height Path Partitioning of Trees

Authors

A. Bagheri ¹
M. Razzazi ²

¹ Department of Computer Engineering and IT,Amirkabir University of Technology

² Department of Computer Science and Engineering,Amirkabir University of Technology

Abstract

Graph partitioning is a well-known problem in the literature. In this paper, path
partitioning of trees in which the given tree is partitioned into edge-disjoint paths is considered. A linear time algorithm is given for computing a path partitioning of minimum height.

Keywords