中山大学学报自然科学版 ›› 2019, Vol. 58 ›› Issue (4): 90-98.doi: 10.13471/j.cnki.acta.snus.2019.04.009

• 论文 • 上一篇    下一篇

Halin图上求解最大切割问题的高效算法

许莉,娄定俊,蒋一帆,秦宗蓉   

  1. 中山大学数据科学与计算机学院,广东 广州 510006
  • 收稿日期:2018-10-11 出版日期:2019-07-25 发布日期:2019-07-25
  • 通讯作者: 娄定俊(1962年生),男;研究方向:图论及算法;E-mail: issldj@mail.sysu.edu.cn

A highly efficient algorithm for maximum cut on Halin graphs

XU Li, LOU Dingjun, JIANG Yifan, QIN Zongrong   

  1. School of Data and Computer Science, Sun Yat-sen University, Guangzhou 51006, China
  • Received:2018-10-11 Online:2019-07-25 Published:2019-07-25

摘要:

对于一个给定的带权图 G=(V,E) ,和一个正整数 k , 是否存在一种切割方法,将 V 划分成两个不相交的子集V1和V2,使得所有一个端点在 V1 中,另一个端点在 V2 中的边的权相加之和大于等于k ? 该问题是在普通图上的一个NPC问题,称为最大切割问题。当各边的权为1时,该问题在普通图上仍是一个NPC问题。提出了一个算法,用于在Halin图上解决最大切割问题,该算法时间复杂度为 O(n),其中n=(|V(G)|。

关键词: 最大切割问题, 可扩性, 收缩扇, 奇面

Abstract:

Given a graph  G=(V,E)  with each edge having a positive integer weight, and a positive integer  k , can V  be partitioned into two disjoint subsets V1 and V2  so that the sum of weights of the edges with one end in V1 and another end in V2 is at least k ? This problem is called the Maximum Cut Problem, which is an NPC problem. When the weight of each edge of G is 1, it is still an NPC problem. A highly efficient algorithm is designed to solve the Maximum Cut Problem with the weight of each edge to be 1 in Halin graphs. The time complexity of the algorithm is  O(n), where n=(|V(G)| .

Key words: maximum cut, extendible, shrinking fan, odd face

中图分类号: