关于图划分问题的改进的近似算法

摘要：

本文考虑NP-难的极大图划分(MAX-GP)问题.我们给出应用半定规划(SDP)松弛的一个一般方法,并且给出包括极大方向割,稠密子图,极大顶点覆盖,极大割,和极大反割在内的图划分问题的改进的近似比.

关键词： 图划分问题 近似算法 半定规划 图论

作者: 徐大川 韩继业

作者单位: 北京工业大学数理学院(北京) 中科院数学与系统科学研究院应用数学所(北京)

会议类型: 国内会议

会议名称: 第六届中国青年运筹与管理学者大会

会议地点: 秦皇岛

会议语种:中文

页码: 156-158

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