Multistars and directed flow formulations

doi:10.1002/net.10050

Multistars and directed flow formulations

2002-10-11

0

PRE

AI

DOI：10.1002/net.10050

Original

Original request for help

Save

Abstract

En 中文

AbstractThe 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.

Multistars and directed flow formulations

Abstract

Journal

Organization

Cited Papers