最多叶子生成树问题的核化算法-计算机学报.PDF

第卷第期 计 算 机 学 报 ３３ １２ 　 　　　　　　　　 Ｖｏｌ．３３Ｎｏ．１２ 年月 ２０１０１２ ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳ Ｄｅｃ．２０１０ 　 最多叶子生成树问题的核化算法 高文宇 （广东商学院信息学院广州 ） ５１０３２０ 　 　 摘要 ， ， 对算法领域的最多叶子生成树问题进行了深入研究提出了对简单连通图度节点的化简规则并证明 ２ 　　 了不含度节点的图的生成树的叶子节点数的下限为（ ）／，给出了构造这样一棵生成树的构造性方法基于 ２ 犖＋６４ ． ２ 上述化简规则和所证明的结论，给出了最多叶子生成树问题的核化算法，该核化算法可以在（）时间内得到一个 犗狀 大小的线性核对于这样一个较小的核，将大大提高相关的参数算法和近似算法的性能 ４犽－６ ． ． 关键词 ； ； 最多叶子生成树核化参数算法 　 中图法分类号 号： ／ ＴＰ３０１ 犇犗犐１０．３７２４ＳＰ．Ｊ．１０１６．２０１０．０２２１１ 　　　 犓犲狉狀犲犾犻狕犪狋犻狅狀犃犾狅狉犻狋犺犿狅犳犕犪狓犻犿狌犿犔犲犪犳犛犪狀狀犻狀犜狉犲犲 犵 狆 犵 ＧＡＯＷｅｎＹｕ （ ， ， ） 犛犮犺狅狅犾狅犆狅犿狌狋犲狉犛犮犻犲狀犮犲犌狌犪狀犱狅狀犝狀犻狏犲狉狊犻狋狅犅狌狊犻狀犲狊狊犛狋狌犱犻犲狊犌狌犪狀狕犺狅狌５１０３２０ 犳 狆 犵犵 狔犳 犵 　 犃犫狊狋狉犪犮狋Ｔｈｉｓａｅｒｒｏｏｓｅｓ２ｄｅｒｅｅｎｏｄｅｒｅｄｕｃｔｉｏｎｒｕｌｅｓｆｏｒＭａｘｉｍｕｍＬｅａｆＳａｎｎｉｎＴｒｅｅ 　 ｐｐｐｐ ｇ ｐ ｇ ， ｒｏｂｌｅｍａｎｄｒｏｖｅｓｔｈａｔａｎｃｏｎｎｅｃｔｅｄｒａｈｗｉｔｈｏｕｔ２ｄｅｒｅｅｎｏｄｅｈａｓａｓａｎｎｉｎｔｒｅｅｉｎｃｌｕ ｐ ｐ ｙ ｇｐ ｇ ｐ ｇ （ ）／ ｄｉｎａ