| 一类布线问题求解的判别准则和算法 |
| |
| 引用本文： | 赵鲁闽,刘彦佩.一类布线问题求解的判别准则和算法[J].北京交通大学学报(自然科学版),2007,31(3):67-71. |
| |
| 作者姓名： | 赵鲁闽 刘彦佩 |
| |
| 作者单位： | 北京交通大学,理学院,北京,100044;北京交通大学,理学院,北京,100044 |
| |
| 摘 要： | 在已有的判决图的基础上,定义了方向性及导出判决图,找到了一个判断布线问题中的1-嵌入问题是否有解的准则和基于此判别准则的算法,并在此基础上进一步研究了禁用构形,找到了1-嵌入问题有解的另一个判别准则.
|
| 关 键 词： | 图论 导出判决图 P构形 始单元 禁用构形 |
| 文章编号： | 1673-0291（2007）03-0067-05 |
| 修稿时间： | 2006-02-21 |
Criterion and Algorithm of Routing Problem |
| |
| ZHAO Lu-min,LIU Yan-pei.Criterion and Algorithm of Routing Problem[J].JOURNAL OF BEIJING JIAOTONG UNIVERSITY,2007,31(3):67-71. |
| |
| Authors: | ZHAO Lu-min LIU Yan-pei |
| |
| Institution: | School of Science, Beijing Jiaotong University, Beijing 100044, China |
| |
| Abstract: | 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. |
| |
| Keywords: | graph induced justment graph P configuration initial unit forbidden configuration |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
