A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms

DOI10.1016/0166-218X(95)00034-OzbMath0854.68071OpenAlexW1967536438MaRDI QIDQ1917270

Nobuhiko Yoshimura, Hiroshi Imai, Yang Dai, Keiji Ohtsuka, Kazuo Iwano, Naoki Katoh

Publication date: 7 July 1996

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(95)00034-o

zbMATH Keywords

multigraphminimum range cut problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems, Minimum dispersion problems, The balanced traveling salesman problem, The quadratic balanced optimization problem

Uses Software

• DIMACS
• NETGEN

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum flow problem is log space complete for P
• A data structure for dynamic trees
• The solution of some random NP-hard problems in polynomial expected time
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• Parallel Merge Sort
• A new approach to the maximum-flow problem
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Efficient parallel algorithms for some graph problems
• An O(logn) parallel connectivity algorithm
• Selected Applications of Minimum Cuts in Networks
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Network Flow and Testing Graph Connectivity
• An Efficient Heuristic Procedure for Partitioning Graphs
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• The Complexity of Multiterminal Cuts
• An Õ(n²) algorithm for minimum cuts