几个图论问题在固定BT模型下的指数下界

摘要：

本文对几个图论问题在固定BT模型下的指数下界进行了研究。文章在固定BT模型下证明了最大割问题下界是Ω(2”n/18”)，最小支配集问题下界是Ω(2”n/19”)，最大独立集问题下界是Ω(2”n/17”)。

关键词： 计算机数学 组合优化 图论问题

作者: 李鑫 刘田 彭瀚 孙宏涛 朱嘉奇

作者单位: 北京大学信息科学技术学院计算机科学技术系,北京,100871

会议类型: 国内会议

会议名称: 2006年全国理论计算机科学学术年会

会议地点: 长春

会议语种:中文

页码: 119-121

在线出版日期: 2006-08-09（万方平台首次上网日期，不代表论文的发表时间）