.png){kind=icon}
.png){kind=icon}
Return
An exact algorithm for Min-Max hyperstructure equipartition with a connected constraint
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2017.05.016.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Hyperstructure is a topological concept that shares characteristics with both graphs and hypergraphs. The Min-Max hyperstructure equipartition with a connected constraint problem consists in partitioning a hyperstructure into K equal-sized connected parts that minimizes the maximum load in each part (the number of hyperedges assigned to each part). This problem, proved to be NP-hard, is an integer nonlinear programming problem. The linearized version of this problem has been introduced. Shrink and Cut algorithm is designed to simplify original complex hyperstructure without changing the optimal solution of the Min-Max hyperstructure equipartition with a connected constraint problem. By the use of this algorithm, Min-Max hyper-tree equipartition with a connected constraint can be solved in polynomial time. An exact algorithm: Min-Max hyperstructure partitioning algorithm, based on a Shrink and Cut algorithm and algorithm S for finding all the spanning trees, is designed to solve ordinary cases, which shows well on experimental results. (C) 2017 Elsevier Ltd. All rights reserved.
Keywords:
Hyperstructure equipartition
NP-Hard
Minimax programming
Connected constraint
Balanced constraint
Rapid transit network
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W