| Author: | Faaland, B. Kim, K. Schmitt, T. |
| Title: | A new algorithm for computing the maximal closure of a graph. |
| Journal: | Management Science
1990 : MAR, VOL. 36:3, p. 315-331 |
| Index terms: | NETWORKS GRAPHS ALGORITHMS |
| Language: | eng |
| Abstract: | A closure in a directed graph is a subset of nodes, all of whose successors belongs 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. A new algorithm is presented for this problem which compares favourably to maximal flow and minimal cut procedures on randomly generated classes of problems. |
SCIMA