在QT-图中寻找最小路覆盖的方法

• 作者: 康玉霞 张华 许成
• 来源期刊: 青岛大学学报(自然科学版)
• 学科: 数学
• 关键词: QT-图 余图 余树 Tad(G) 最小路覆盖
• 年，卷（期）: 2007,（3）
• 所属期刊栏目: 数学
• 页码范围: 26-29
• 页数: 4页
• 分类号: O157
• 字数: 2522字
• 语种: 中文
• DOI: 10.3969/j.issn.1006-1037.2007.03.007

摘要

主要给出了QT-图(quasi-threshold graph)中两种寻找最小路覆盖的方法.假设QT-图G有m条边, n个顶点,首先,应用余图中寻找最小路覆盖的思想来解决QT-图中此类问题,其算法复杂性为O(n);第2,根据QT-图的Tad(G)(即available-dummy tree)的构造,建立了一种解决此类问题的新算法,并给出了算法的正确性说明,它的算法复杂性为O(logn).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	许成	青岛大学数学科学学院	29	46	3.0	5.0
2	张华	青岛大学数学科学学院	54	212	7.0	12.0
3	康玉霞	青岛大学数学科学学院	2	1	1.0	1.0