Mazimum Connected Domatic Partition of Directed Path Graphs with Single Junction

摘要：

In this paper, we consider the problem of finding a maximum connected domatic partition of a given graph. We propose a polynomial time algorithm for solving the problem for a subclass of directed path graphs which is known as a class of intersection graphs modeled by a set of directed paths on a directed tree. More specifically, we restrict the class of directed path graphs in such a way that the underlying directed tree has at most one node to have several incoming arcs.

作者: Masaya Mito Satoshi Fujita

作者单位: Department of Information Engineering Graduate School of Engineering, Hiroshima University

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 425-433

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）