Divide-and-conquer minimal-cut bisectioning of task graphs

被引：0

作者：

Lor, S

Shen, H

Maheshwari, P

机构：

来源：

COMPUTER SYSTEMS SCIENCE AND ENGINEERING | 1996年 / 11卷 / 04期

关键词：

combinatorial problems; graph partitioning; heuristic algorithms; mapping problem; parallel processing;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This paper proposes a method for partitioning the vertex set of an undirected simple weighted graph into two subsets so as to minimise the difference of vertex-weight sums between the two subsets and the total weight of the edges cut (i.e. edges with one end in each subset). The proposed heuristic algorithm works in a divide-and-conquer fashion and is a modification of an algorithm suggested in the literature. The algorithm has the same time complexity as the previous one but is extended to work on weighted graphs.

引用

页码：227 / 234

页数：8

共 10 条

[1] Divide-and-conquer mapping of parallel programs onto hypercube computers
Lor, S
Shen, H
Maheshwari, P
JOURNAL OF SYSTEMS ARCHITECTURE, 1997, 43 (6-7) : 373 - 390
[2] Efficient Divide-and-Conquer Implementations of Symmetric FSAs
Pritchard, David A. G.
JOURNAL OF CELLULAR AUTOMATA, 2010, 5 (06) : 481 - 490
[3] A Flexible Divide-and-Conquer MPSoC Architecture for MIMO Interference Cancellation
Yuan, Luechao
Liu, Cang
Tang, Chuan
Huang, Shan
Chattopadhyay, Anupam
Ascheid, Gerd
Xing, Zuocheng
IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 2017, 25 (10) : 2789 - 2802
[4] Scaling Up Dynamic Optimization Problems: A Divide-and-Conquer Approach
Yazdani, Danial
Omidvar, Mohammad Nabi
Branke, Juergen
Trung Thanh Nguyen
Yao, Xin
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2020, 24 (01) : 1 - 15
[5] A Fast Divide-and-Conquer Algorithm for Indexing Human Genome Sequences
Loh, Woong-Kee
Moon, Yang-Sae
Lee, Wookey
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2011, E94D (07): : 1369 - 1377
[6] Performance Analysis of Divide-and-Conquer strategies for Large scale Simulations in R
Subramanian, Ranjini
Zhang, Hui
2018 IEEE INTERNATIONAL CONFERENCE ON BIG DATA (BIG DATA), 2018, : 4261 - 4267
[7] A parallel processing method of divide-and-conquer and a highly efficient parallel sorting algorithm
Huang, Minghe
Zhong, Cuixiang
Dai, Liping
Lei, Gang
DCABES 2006 Proceedings, Vols 1 and 2, 2006, : 86 - 88
[8] An efficient divide-and-conquer technique for parallel computation of modular multi-exponentiation
Lou, DC
Chang, CC
COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 2000, 15 (02): : 111 - 117
[9] A Divide-and-Conquer Evolutionary Algorithm for Large-Scale Virtual Network Embedding
Song, An
Chen, Wei-Neng
Gong, Yue-Jiao
Luo, Xiaonan
Zhang, Jun
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2020, 24 (03) : 566 - 580
[10] Minimal 2-connected graphs satisfying the even cut condition
Jobson, Adam S.
Kezdy, Andre E.
Lehel, Jeno
INFORMATION PROCESSING LETTERS, 2021, 167

← 1 →