| 在QT-图中寻找最小路覆盖的方法 |
| |
| 引用本文： | 张华,许成,康玉霞. 在QT-图中寻找最小路覆盖的方法[J]. 青岛大学学报(自然科学版), 2007, 20(3): 26-29 |
| |
| 作者姓名： | 张华 许成 康玉霞 |
| |
| 作者单位： | 青岛大学,数学科学学院,青岛,266071;青岛大学,数学科学学院,青岛,266071;青岛大学,数学科学学院,青岛,266071 |
| |
| 摘 要： | 主要给出了QT-图（quasi-threshold graph）中两种寻找最小路覆盖的方法。假设QT-图G有m条边,n个顶点,首先,应用余图中寻找最小路覆盖的思想来解决QT-图中此类问题,其算法复杂性为O（n）;第2,根据QT-图的Tad（G）（即available-dummy tree）的构造,建立了一种解决此类问题的新算法,并给出了算法的正确性说明,它的算法复杂性为O（logn）。
|
| 关 键 词： | QT-图 余图 余树 Tad(G) 最小路覆盖 |
| 文章编号： | 1006-1037（2007）03-0026-04 |
| 收稿时间： | 2007-04-19 |
| 修稿时间： | 2007-04-19 |
Algorithms on a Minimum Path Cover Problem in QT-Graph |
| |
| ZHANG Hua,XU Cheng,KANG Yu-xia. Algorithms on a Minimum Path Cover Problem in QT-Graph[J]. Journal of Qingdao University(Natural Science Edition), 2007, 20(3): 26-29 |
| |
| Authors: | ZHANG Hua XU Cheng KANG Yu-xia |
| |
| Affiliation: | College of Mathematical Science, Qingdao University, Qingdao 266071, China |
| |
| Abstract: | |
| |
| Keywords: | Tad(G) |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
