A New Algorithm for Computing the Maximal Closure of a Graph

1990/03/01 by Bruce Faaland, Kiseog Kim, Tom Schmitt · 17 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Computational Geometry and Mesh Generation #Closure (psychology) #Closure problem #Mathematics #Maximum flow problem #Algorithm #Directed graph #Graph #Minimum cut #Node (physics) #Combinatorics #Discrete mathematics

paper · doi:10.1287/mnsc.36.3.315

published in Management Science 36(3), 315-331 (Institute for Operations Research and the Management Sciences)

openalex publication_date 1990/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

A closure in a directed graph is a subset of nodes, all of whose successors belong to the subset. If each node has an assigned weight, which may be positive or negative, the maximal closure problem is one of finding a closure with the largest possible sum of node weights. It can be solved by any maximal flow or minimal cut algorithm. We present a new algorithm for this problem which compares favorably to maximal flow and minimal cut procedures on randomly generated classes of problems.

Citations

• An O(|V|3) algorithm for finding maximum flows in networks
• Maximal Closure of a Graph and Applications to Combinatorial Problems
• A Selection Problem of Shared Fixed Costs and Network Flows

Cited by

• Closure problem [wikipedia]