弦图扩张与最优排序

Chordal Graph Extension and Optimal Sequencing

弦图是一类特殊的完美图，以具有完美消去顺序为特征．由弦图扩张引出一系列序列性组合优化问题，沟通了图论、数值分析及最优排序等领域的若干研究课题．本文将论述我们的一些观点和研究结果．

Chordal graphs are special perfect graphs that have the pecfect elimination order,and interval graphs are special chordal graphs. This survey studies a class of optimal sequencing problems (including the fill-in,profile,treewidth and pathwidth,etc) in a view-point of chordal and interval graph extensions.