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