超图在树环中的嵌入问题

作者：王琦; 赵秀恒; 李国君

来源：山东大学学报(理学版), 2007, (10): 114-117.

DOI：10.3969/j.issn.1671-9352.2007.10.025

• 树环
• PTAS
• 支撑树

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优嵌入使得G中任一边被H所有超边的嵌入经过的最大次数最小.将超图嵌入圈(MCHEC)问题的算法简化可得EHTR问题的一个PTAS算法,且可证明EHTR问题为NP-完全的.

• 出版日期2007
• 单位山东大学; 河北经贸大学