摘要
主要给出了QT-图(quasi-threshold graph)中两种寻找最小路覆盖的方法。假设QT-图G有m条边,n个顶点,首先,应用余图中寻找最小路覆盖的思想来解决QT-图中此类问题,其算法复杂性为O(n);第2,根据QT-图的Tad(G)(即available-dummy tree)的构造,建立了一种解决此类问题的新算法,并给出了算法的正确性说明,它的算法复杂性为O(logn)。
This paper introduces two algorithms on a minimum path cover problem in QT- graph（the abbreviation of quasi-threshold graph） G which has m edges and n vertices. One is that we can use the thought of minimum path cover of cograph to solve this kind of problem in QT - graph. This algorithm needs O（n） time. The other is the new algorithm which is produced according to the construction of Tad（G） （the abbreviation of available-dummy tree）. Here we show the correctness of the new algorithms and they it run in O（log n） time.
出处
《青岛大学学报（自然科学版）》
CAS
2007年第3期26-29,共4页
Journal of Qingdao University(Natural Science Edition)
