Premium
Multistars and directed flow formulations
Author(s) -
Gouveia Luis,
Hall Leslie
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10050
Subject(s) - mathematics , polynomial , directed graph , class (philosophy) , time complexity , combinatorics , equivalence (formal languages) , tree (set theory) , discrete mathematics , computer science , mathematical analysis , artificial intelligence
Abstract The Capacitated Minimum Spanning Tree Problem seeks a least‐cost spanning tree subject to a bound imposed on the number of nodes in each subtree pending from a given root node. Araque et al. (Technical Report SOR‐90‐12, Princeton University, 1990) introduced several classes of facet‐defining inequalities for the undirected version of the problem, most of which have straightforward analogs to the directed version and are also facet‐defining in that case (see Zhang, Master's thesis, 1993). The multistar constraints are one such class. Gouveia [Telecommun Syst 1 (1993), 51–56] showed that a directed flow formulation gives a polynomial representation of the class of directed multistar constraints. This equivalence shows how to obtain a polynomial‐time separation algorithm for this class of inequalities. In this paper, we show that the previous equivalence result implies that we can also separate in polynomial time the exponential‐sized class of undirected multistar constraints. We also show that “using a directed model” plays a key role in obtaining a polynomial‐time separation algorithm for this class of inequalities, that is, using a directed flow model seems to be crucial for obtaining a polynomial‐time separation algorithm for the class of undirected multistar constraints. © 2002 Wiley Periodicals, Inc.