CAJ | 학술논문

根据用户解释的特点和问题求解的需要扩充了图论中有向图的定义,使其结点既可以是普通的结点,又可以是一个有向图,并把用于表示用户解释的这种有向图称为GD-约束图.在此基础上,对不含冲突的用户解释表现于GD-约束图中的特征进行了抽取.最后,总结出用户解释不含冲突的充要条件并根据这个充要条件提出了一个时间复杂性为O(m×n)的多项式时间识别算法,同时还对算法的正确性和时间复杂性进行了证明和分析.
근거용호해석적특점화문제구해적수요확충료도론중유향도적정의,사기결점기가이시보통적결점,우가이시일개유향도,병파용우표시용호해석적저충유향도칭위GD-약속도.재차기출상,대불함충돌적용호해석표현우GD-약속도중적특정진행료추취.최후,총결출용호해석불함충돌적충요조건병근거저개충요조건제출료일개시간복잡성위O(m×n)적다항식시간식별산법,동시환대산법적정학성화시간복잡성진행료증명화분석.