A new algorithm for computing the maximal closure of a graph

A new algorithm for computing the maximal closure of a graph

0.00 Avg rating0 Votes
Article ID: iaor1990616
Country: United States
Volume: 36
Issue: 3
Start Page Number: 1
End Page Number: 7
Publication Date: Mar 1990
Journal: Management Science
Authors: , ,
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. The authors present a new algorithm for this problem which compares favorably to maximal flow and minimal cut procedures on randomly generated classes of problems.

Reviews

Required fields are marked *. Your email address will not be published.