组合最优化中的排序,标号与嵌入

本项目的研究内容包括组合最优化中的三个课题：排序、标号与嵌入。三年内共发表学术论文20余篇，其中15篇为列入本报告的代表作，并出版两部专著。主要成果如下：第一，关于最优排序问题，探讨以阵、独立系统及凸性刻划为理论工具的统一方法，对最优解的结构性质及求解途径得到较普遍的理论结果。第二，关于最优标号问题，将传统的标号问题（带这贡、割宽、侧廓、填充等）与图子式理论及VLSI设计等前沿领域提出的树宽、路宽等问题沟通起来，形成以统图扩张为中心的一个新方向。第三，关于最优嵌入问题，改进了二维网格嵌入的浓度下界；建立了环嵌入（循环带宽）的基本理论，解决了若干特征刻划问题。总之，本项目较圆满地完成了预定 计划。