系列平行图上带时间约束的Steiner最小树问题  

A delay constrained Steiner minimum tree problem in series-parallel graphs

作　　者：陈光亭[1] 

机构地区：[1]杭州电子科技大学运筹与控制研究所,浙江杭州310018

出　　处：《高校应用数学学报（A辑）》2008年第1期30-34,共5页Applied Mathematics A Journal of Chinese Universities(Ser.A)

基　　金：国家自然科学基金(10371028);浙江省教育厅重点资助项目(20030622)

摘　　要：对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.The NP-hardness of a delay constrained Steiner minimum tree problem in a special series-paraUel graph is proved in this paper,and a fully polynomial time approximation scheme is presented.

关 键 词：Steiner最小树 系列平行图 多项式时间近似方案 

分 类 号：O157.5[理学—数学]