A Warning Propagation Algorithm for Solving Minimum Cut

WANG Xin; WANG Xiao-feng; LI Wei-min

doi:10.3969/j.issn.0372-2112.2019.11.021

您当前的位置：

首页 >

文章列表页 >

A Warning Propagation Algorithm for Solving Minimum Cut

更新时间：2025-07-16

- A Warning Propagation Algorithm for Solving Minimum Cut
- Acta Electronica Sinica Vol. 47, Issue 11, Pages: 2386-2391(2019)
- 作者机构：
  
  1. 北方民族大学计算机科学与工程学院,宁夏,银川,750021
  2. 上海大学计算机工程与科学学院,上海,200444
  3. 北方民族大学计算机科学与工程学院,宁夏,银川,750021
  4. 上海大学计算机工程与科学学院,上海,200444
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2019.11.021
  CLC： TP301
- Published Online：25 November 2019，
  
  Published：2019
- 稿件说明：
移动端阅览
WANG Xin, WANG Xiao-feng, LI Wei-min. A Warning Propagation Algorithm for Solving Minimum Cut[J]. Acta Electronica Sinica, 2019, 47(11): 2386-2391.
DOI：

WANG Xin, WANG Xiao-feng, LI Wei-min. A Warning Propagation Algorithm for Solving Minimum Cut[J]. Acta Electronica Sinica, 2019, 47(11): 2386-2391. DOI： 10.3969/j.issn.0372-2112.2019.11.021.

摘要

最小割问题（minimum cut problem）是NP（Non-deterministic Polynomial）难问题，警示传播算法（warning propagation）是一种基于因子图的消息传递算法，可用于求解组合优化问题.首先，本文借助隐马尔可夫模型将无向图转换为因子图，将求解最小割映射为求解因子图的相应问题.进而设计一种求解最小割的警示传播算法.最后，选取了几组随机无向图实例进行数值实验，实验结果表明，该算法在求解速度上优于同类算法.

Abstract

The minimum cut problem (MCP) is an NP (Non-deterministic Polynomial)-hard problem

warning propagation (WP) is a kind of message passing algorithm based on factor graph

it solve the combinatorial optimization problem.First

HMM (Hidden Markov Model) converted undirected graph to factor graph.Then

we designed a kind of warning propagation algorithm to solving the minimum cut.Finally

we selected skit randomly undirected graphs numerical experiments.The experimental show that the algorithm precedes similar algorithms in speed.

关键词

Keywords

references

Views

183

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

One Hybrid Strategy for Automatic Placement and Routing of QCA Circuit

Research of Lung Cancer Recognition Based on Chest CT Images

A Study of Optimum Multiuser Detection Problem

A Novel Improved Quantum Genetic Algorithm for Combinatorial Optimization Problems

Research on Polynomial-Fitting Speech-Trajectory Model in Chinese Continuous Speech Recognition

Related Author

XIE Guang-jun

LI Xiao-shuai

HAN Qian

PENG Fei

LI Yang-shuai

HE Wei

JIANG Hui-yan

WANG Shao-wei

Related Institution

College of Microelectronics， Hefei University of Technology

College of Electronic Engineering， National University of Defense Technology

School of Software,Northeastern University

Department of Electronic Science and Engineering,Nanjing University

School of Telecommunication EngineeringBeijing University of Posts and TelecommunicationsBeijing 100876China

⁰