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
• DOI: 10.1016/s0304-3975(98)00180-7

✦ 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.