An exact algorithm for min-max hyperstructure equipartition with a connected constraint

DOI10.1016/J.COR.2017.05.016MaRDI QIDQ1652415zbMATH OpenOpenAlexFDO

Authors Tunzi Tan, Juan A. Mesa, Suixiang Gao

Publication date 11 July 2018

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2017.05.016

zbMATH Keywords

NP-hardrapid transit networkminimax programmingbalanced constraintconnected constrainthyperstructure equipartition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Minimax problems in mathematical programming (90C47) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Computing minimum multiway cuts in hypergraphs
• Computing minimum multiway cuts in hypergraphs from hypertree packings
• Solution of one problem of optimal partition of the vertex set of a hypergraph
• An efficient algorithm for judicious partition of hypergraphs
• scientific article; zbMATH DE number 2075198

Cites work

• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3630603 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2075198 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3296025 (Why is no real title available?)
• A Globally Convergent Augmented Lagrangian Algorithm for Optimization with General Constraints and Simple Bounds
• A branch-and-cut algorithm for the equicut problem
• An \(O(k^ 2 n^ 2)\) algorithm to find a \(k\)-partition in a \(k\)- connected graph
• An \(\mathcal{O}(n^4)\) time algorithm to compute the bisection width of solid grid graphs
• An effective multilevel tabu search approach for balanced graph partitioning
• An exact algorithm for graph partitioning
• Approximation and inaproximability results on balanced connected partitions of graphs
• Equipartitions of graphs
• Fast Approximate Graph Partitioning Algorithms
• Graph Partitioning and Graph Clustering
• How to draw a hypergraph
• Hypergraph theory. An introduction
• Hyperstructures, a new approach to complex systems
• Line graphs for a multiplex network
• Min-Max Graph Partitioning and Small Set Expansion
• Min-cut clustering
• On the complexity of partitioning graphs into connected subgraphs
• On the validity of a front-oriented approach to partitioning large sparse graphs with a connectivity constraint
• Partitioning graphs into balanced components
• Recent directions in netlist partitioning: a survey
• Solving Graph Bisection Problems with Semidefinite Programming
• Some simplified NP-complete graph problems
• The TOMLAB optimization environment in MATLAB

Cited in

(2)

• Constrained Min-Cut Replication for K-Way Hypergraph Partitioning
• A global method for the limited K-partitioning of hypergraphs representing optimal design problems in complex machine systems

Describes a project that uses

Uses Software

• Chaco
• TOMLAB
• OPERA
• NLPLIB

This page was built for publication: An exact algorithm for min-max hyperstructure equipartition with a connected constraint

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1652415)