摘要
在已有的判决图的基础上,定义了方向性及导出判决图,找到了一个判断布线问题中的1-嵌入问题是否有解的准则和基于此判别准则的算法,并在此基础上进一步研究了禁用构形,找到了1-嵌入问题有解的另一个判别准则.
Based on the justment graph, the orientation and induced justment graph is defined. A criterion for the solvability of the 1-embedding problems in the routing problems is found. An algorithm for determining a 1-embedding is decided whenever the 1-embedding problem has a solution. Further, the forbidden configuration for the solvability is discussed, so the that another criterion is reached.
出处
《北京交通大学学报》
EI
CAS
CSCD
北大核心
2007年第3期67-71,共5页
JOURNAL OF BEIJING JIAOTONG UNIVERSITY
关键词
图论
导出判决图
P构形
始单元
禁用构形
graph
induced justment graph
P configuration
initial unit
forbidden configuration
