๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Optimal path cover problem on block graphs

โœ Scribed by Wong Pak-Ken


Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
427 KB
Volume
225
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

โœฆ Synopsis


Let G = (V,E) be a block graph. First we show that an algorithm for finding the path partition number p(G) by J.H. Yan and G.J. Chang gives wrong answers to some block graphs. Then we present an efficient algorithm for finding a minimum path partition of G (not just the path partition number p(G)). The complexity of this algorithm is O(m), where m = IEl.


๐Ÿ“œ SIMILAR VOLUMES