- 1 BENDERS J.F Partmomng procedures for solving mixed-variables programming problems Numer. ische Math. 4 (1962), 238-252.Google Scholar
- 2 Chandy, K.M, ANI) Lo, T. The capacttated muumum spanning tree. Networks 3, 2 (1973), 173-182.Google Scholar
- 3 DArnTZIG, G.B., AND WOLFE, PThe decomposition algorithm for linear programming. Econometrica 29, 4 (1961), 10t-111.Google Scholar
- 4 DIJKSTRA, E W. A note on two problems m connection with graphs. Numerische Math. 1 (1959), 269-271Google Scholar
- 5 ELIAS, D., AND FERGUSON, M J Topological design of mulUpoint teleprocessmg networks IEEE Trans. Commun. COM-22 (197#), 1753-1762.Google Scholar
- 6 ESSAU, L.R., AND WILLXA~S, K C.On teleprocessmg system design, IBM Syst J 5, 3 (1966), 142-147.Google Scholar
- 7 Fisher, M.L.The Langrangian relaxation method for solving integer programming problems. Manage Sci. 27, 1 (1981), 1-18.Google Scholar
- 8 GABOW, H.N A good algorithm for smallest spanning trees wtth a degree constraint. Networks 8 (1978), 201-208.Google Scholar
- 9 GAVlSR, B.New algorithms for the capacitated mimmal directed tree problem. Proc 1980 IEEE Int. Conf on Circuits and Computers, Port Chester, N.Y., Oct. 1980, pp 996-1000Google Scholar
- 10 GAVISH, B.Topological design of centralized computer networks--FormulaUons and algorRluns. Networks (to appear)Google Scholar
- 11 GAVISH, B., AND HANTLER, S. A Lagranglan relaxation procedure for optimal route selection m SNA networks. Workmg Paper, Graduate School of Management, Univ. of Rochester, Rochester, N.Y., 1982.Google Scholar
- 12 GAriSH, B., ^r~I~ SRIKANTIt, K N. O(Nz) algorithms for sensativlty analysis of miatmal spanning trees and related subgraphs D~screte Appl Math. (to appear)Google Scholar
- 13 GAVISH, B, AND SRIKANTH, K N. Optmaal solution methods for large-scale multiple-salesmen traveling salesman problem. Manage. Sct (to appear).Google Scholar
- 14 GI~OrFR}ON, A.M.Ggrangtan relaxation and its uses m integer programming. Math Program. Study 2 (1974), 82-114Google Scholar
- 15 HELD, M., AND KAnt, R.M The traveling salesman problem and minimum sparmmg trees, Part 1. Oper. Res 18 (1970), 1138-1162.Google Scholar
- 16 HELD, M., AND KARP, R.M The travehng salesman problem and mimmum spanning trees, Part II. Math. Progrant 1 (1971), 6-25.Google Scholar
- 17 HELD, M., WOLFE, P, AND CROWDER, H P Vahdatton of subgradient optimizauon. Math Program. 6 (1974), 62-88.Google Scholar
- 18 KARNAU6n, M A new class of algorithms for multapomt network optimization IEEE Trans. Commun C-24, 5 (1976), 500-505.Google Scholar
- 19 Kr_e, ZHENBAUM, A.Computing capaotated mmmaal spanning trees efficiently Networks 4, 4 (1974), 299-310.Google Scholar
- 20 K~RSHENBAtrM, A., AND BOORSTYN, R R. Centralized teleprocessmg network design. Proc. Nat. Telecommumcauon Conf, New Orleans, La., 1975, pp 2711-2714.Google Scholar
- 21 KERSHENBAUM, A., AND BOORS'rYN, R.R Centralized teleprocessing network design. IEEE Trans. Commun. (to appear).Google Scholar
- 22 KE~SH~aAtJM, A, BOORSTYN, R R, AND OPPENHE1M, R. Second-order greedy algorithms for centralmed teleprocessmg network design. IEEE Trans Commun. (to appear).Google Scholar
- 23 PAPADIMITRIOU, C H.The complexity of the capacitated tree problem. Networks 8 (1978), 217-230.Google Scholar
- 24 POLJACK, B T A general method of solwng extremum problems. Soy Math Doklady 8 (1967), 593-597.Google Scholar
Index Terms
- Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
Recommendations
Local search algorithms for the k-cardinality tree problem
In this paper we deal with an NP-hard combinatorial optimization problem, the k-cardinality tree problem in node-weighted graphs. This problem has several applications, which justify the need for efficient methods to obtain good solutions. We review ...
A filter-and-fan algorithm for the capacitated minimum spanning tree problem
The capacitated minimum spanning tree (CMST) is a notoriously difficult problem in combinatorial optimization. Extensive investigation has been devoted to developing efficient algorithms to find optimal or near-optimal solutions. This paper proposes a ...
Randomized heuristics for the Capacitated Clustering Problem
In this paper, we investigate the adaptation of the Greedy Randomized Adaptive Search Procedure (GRASP) and Iterated Greedy methodologies to the Capacitated Clustering Problem (CCP). In particular, we focus on the effect of the balance between ...
Comments