论文部分内容阅读
根据用户解释的特点和问题求解的需要扩充了图论中有向图的定义 ,使其结点既可以是普通的结点 ,又可以是一个有向图 ,并把用于表示用户解释的这种有向图称为 GD-约束图 .在此基础上 ,对不含冲突的用户解释表现于 GD-约束图中的特征进行了抽取 .最后 ,总结出用户解释不含冲突的充要条件并根据这个充要条件提出了一个时间复杂性为 O(m× n)的多项式时间识别算法 ,同时还对算法的正确性和时间复杂性进行了证明和分析