Maximal Closure of a Graph and Applications to Combinatorial Problems

Jean-Claude Picard
Additional contact information
Jean-Claude Picard: Ecole Polytechnique, Montreal

Management Science, 1976, vol. 22, issue 11, 1268-1272

Abstract: This paper generalizes the selection problem discussed by J. M. Rhys [Rhys, J. M. W. 1970. Shared fixed cost and network flows. Management Sci. 17 (3, November).], J. D. Murchland [Murchland, J. D. 1968. Rhys's combinatorial station selection problem. London Graduate School of Business Studies, Transport Network Theory Unit, Report LBS-TNT-68, June 10.], M. L. Balinski [Balinski, M. L. 1970. On a selection problem. Management Sci. 17 (3, November).] and P. Hansen [Hansen, P. 1974. Quelques approches de la programmation non lineaire en variables 0-1. Conference on Mathematical Programming, Bruxelles, May.]. Given a directed graph G, a closure of G is defined as a subset of nodes such that if a node belongs to the closure all its successors also belong to the set. If a real number is associated to each node of G a maximal closure is defined as a closure of maximal value.

Date: 1976
References: Add references at CitEc
Citations: View citations in EconPapers (40)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.22.11.1268 (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:22:y:1976:i:11:p:1268-1272

Access Statistics for this article

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