带权最大割问题的一种关于划分技术的固定参数可解算法.pdfVIP

高技术通讯20 10 年第20 卷第3 期：264 ~ 269 doi ：10 . 3772 . issn. 1002-0470 . 2010 . 03. 008 带权最大割问题的一种基于划分技术的固定参数可解算法! 刘运龙 王建新 （ 中南大学信息科学与工程学院 长沙4 10083 ） （ 湖南师范大学继续教育学院 长沙4 10013 ） 摘 要 运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题 及其相关概念进行了参数化定义，然后对参数化带权最大割问题提出了一种基于随机划 分技术的随机算法。该随机算法依次将实例图的顶点进行 「In（1 ! ）」 2 （0 ! 1 ） 次随机划分，并选择其中权值最大的 -划分作为输出解，因而能在时间 （In（1 ! ）2 ） 内以至少1 ! 的概率找到目标解。接着在此基础上着重运用必威体育精装版改进的（ ， ）-全集划 分技术对参数化带权最大割问题提出了一个时间复杂度为 （22 12Iog2 （2 ））的确定性算 法，表明了带权最大割问题是固定参数可解的。 关键词 带权最大割问题，固定参数可解，随机划分，（ ， ）-全集 表示该个割。对于图 的任意一个割（ ， ）和任意 0 引言 一条边 ，如果边 的一个端点属于 ，另一个端点 属于 ，本文简称割（ ， ）含有边 或者边 属于割 带权的最大割问题是计算复杂性理论中一个经 （ ， ）。 典的NP 难解问题，在电路设计和统计物理学中有 ［5 ］ ［1］ 定义 （参数化最大割问题 ） 给定一个无 着广泛的实际应用 。自从 1972 年被证明是 NP 难的以来，该问题一直是近似计算领域中的一个主 向图 （ ， ）和一个正整数 ，目标是判定图 ［2-4 ］ 是否存在一个规模至少为 的割。 要研究对象 。在参数计算复杂性领域近年来人 们也开始关注了该问题，但当前的研究主要集中于该 同样，本文称图 的一个规模至少为 的割为 问题的特殊情况，即研究参数化的最大割问题［5-7 ］。 图 的一个 -割（或 -划分），并用符号 -cut 表示。 ［1］ 本文的主要工作是对参数化带权的最大割问题进行 定义# （带权的最大割问题 ） 对于一个无 研究，并对该问题设计有效的固定参数可解算法，即 向图 = （ ， ），其中每一条边（ ， ） 都带有一