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

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

doi:10.13471/j.cnki.acta.snus.2019.04.009

您当前的位置：

首页 >

文章列表页 >

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

论文 | 更新时间：2023-12-11

- Halin图上求解最大切割问题的高效算法
- A highly efficient algorithm for maximum cut on Halin graphs
- 中山大学学报(自然科学版)(中英文) 2019年58卷第4期页码：90-98
- 作者机构：
  
  中山大学数据科学与计算机学院,广东,广州,510006
- 作者简介：
- 基金信息：
- DOI：10.13471/j.cnki.acta.snus.2019.04.009
  中图分类号：
- 纸质出版日期：2019，
  
  网络出版日期：2019-7-25，
扫描看全文
许莉, 娄定俊, 蒋一帆, 等. Halin图上求解最大切割问题的高效算法[J]. 中山大学学报(自然科学版)(中英文), 2019,58(4):90-98.

XU Li, LOU Dingjun, JIANG Yifan, et al. A highly efficient algorithm for maximum cut on Halin graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2019,58(4):90-98.
许莉, 娄定俊, 蒋一帆, 等. Halin图上求解最大切割问题的高效算法[J]. 中山大学学报(自然科学版)(中英文), 2019,58(4):90-98. DOI： 10.13471/j.cnki.acta.snus.2019.04.009.

XU Li, LOU Dingjun, JIANG Yifan, et al. A highly efficient algorithm for maximum cut on Halin graphs[J]. Acta Scientiarum Naturalium Universitatis SunYatseni, 2019,58(4):90-98. DOI： 10.13471/j.cnki.acta.snus.2019.04.009.

摘要

对于一个给定的带权图

G=(V

和一个正整数

是否存在一种切割方法，将

划分成两个不相交的子集

和

使得所有一个端点在

中，另一个端点在

中的边的权相加之和大于等于

? 该问题是在普通图上的一个NPC问题，称为最大切割问题。当各边的权为1时，该问题在普通图上仍是一个NPC问题。提出了一个算法，用于在Halin图上解决最大切割问题，该算法时间复杂度为 O(

)，其中n=(|

(

)|。

Abstract

Given a graph

G=(V

with each edge having a positive integer weight

and a positive integer

can

be partitioned into two disjoint subsets

and 

so that the sum of weights of the edges with one end in

and another end in

is at least

? 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(

)， where n=(|

(

)| .

关键词

最大切割问题可扩性收缩扇奇面

Keywords

maximum cutextendibleshrinking fanodd face

references

浏览量

113

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据