论文部分内容阅读
本文对几个图论问题在固定BT模型下的指数下界进行了研究。文章在固定BT模型下证明了最大割问题下界是Ω(2[n/18])，最小支配集问题下界是Ω(2[n/19])，最大独立集问题下界是Ω(2[n/17])。
几个图论问题在固定BT模型下的指数下界
【摘 要】
：
本文对几个图论问题在固定BT模型下的指数下界进行了研究。文章在固定BT模型下证明了最大割问题下界是Ω(2[n/18])，最小支配集问题下界是Ω(2[n/19])，最大独立集问题下界是Ω(2
【机 构】
：
北京大学信息科学技术学院计算机科学技术系,北京,100871
【出 处】
：
2006年全国理论计算机科学学术年会
【发表日期】
：
2006年期
其他文献