A New Algorithm for Computing the Maximal Closure of a Graph

Bruce Faaland, Kiseog Kim and Tom Schmitt
Additional contact information
Bruce Faaland: Graduate School of Business, University of Washington, Seattle, Washington 98195
Kiseog Kim: Pusan National Unversity, Pusan, Republic of Korea
Tom Schmitt: Graduate School of Business, University of Washington, Seattle, Washington 98195

Management Science, 1990, vol. 36, issue 3, 315-331

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.

Keywords: graphical algorithms; network flow; minimum cuts (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.36.3.315 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:36:y:1990:i:3:p:315-331

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().