The minimum spanning tree problem with time window constraints. (English) Zbl 0634.90046
In the spanning tree problem with time window constraints it is desired to find a minimum cost spanning tree directed from a specified root node such that the window constraints on the nodes are satisfied.
This paper first shows that the problem above is NP-hard, and then gives two heuristic algorithms: greedy and insertion. Finally it is reported that the computational experience indicates that the insertion heuristic is much better than the greedy.
This paper first shows that the problem above is NP-hard, and then gives two heuristic algorithms: greedy and insertion. Finally it is reported that the computational experience indicates that the insertion heuristic is much better than the greedy.
Reviewer: J.Zhu
MSC:
| 90C10 | Integer programming |
| 65K05 | Numerical mathematical programming methods |
| 58C25 | Differentiable maps on manifolds |
| 90C27 | Combinatorial optimization |
| 90C35 | Programming involving graphs or networks |
| 05C05 | Trees |
Keywords:
computational performance; computational complexity; spanning tree; time window constraints; NP-hard; heuristic algorithms; greedy; insertionReferences:
| [1] | Bodin L., Computers and Operations Research 10 pp 62– (1983) |
| [2] | Chandy K., Networks 3 pp 173– (1973) · Zbl 0256.90016 · doi:10.1002/net.3230030204 |
| [3] | Christofides N., Mathematical Programming 20 pp 255– (1981) · Zbl 0461.90067 · doi:10.1007/BF01589353 |
| [4] | Christofides N., Combinatorial Optimization pp 315– (1979) · Zbl 0401.00019 |
| [5] | Dijkstra E., Numerische Mathematik 1 pp 269– (1959) · Zbl 0092.16002 · doi:10.1007/BF01386390 |
| [6] | Edmonds J., National Bureau of Standards 7 pp 233– (1967) · Zbl 0155.51204 · doi:10.6028/jres.071B.032 |
| [7] | Garey M., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979) · Zbl 0411.68039 |
| [8] | Gavish B., Networks 12 pp 355– (1982) · Zbl 0493.94021 · doi:10.1002/net.3230120402 |
| [9] | Gavish B., Journal of the Association for Computing Machinery 30 pp 118– (1983) · Zbl 0504.90052 · doi:10.1145/322358.322367 |
| [10] | Gavish B., Augmented lagrangean based algorithms for solving capacitated minimal spanning tree problems (1983) |
| [11] | Golden B., Networks 7 pp 113– (1977) · Zbl 0359.90054 · doi:10.1002/net.3230070203 |
| [12] | Held M., Operations Research 18 pp 1138– (1970) · Zbl 0226.90047 · doi:10.1287/opre.18.6.1138 |
| [13] | Held M., Mathematical Programming 1 pp 6– (1971) · Zbl 0232.90038 · doi:10.1007/BF01584070 |
| [14] | Kershenbaum A., Networks 4 pp 299– (1974) · Zbl 0311.90070 · doi:10.1002/net.3230040403 |
| [15] | Kruskal J., Proceedings of the American Mathematical Society 7 pp 48– (1956) · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7 |
| [16] | Prim R., Bell Systems Technical Journal 36 pp 1389– (1957) · doi:10.1002/j.1538-7305.1957.tb01515.x |
| [17] | Shogan A., Networks 13 pp 169– (1983) · doi:10.1002/net.3230130203 |
| [18] | Solomon M., Operations Research (1983) |
| [19] | Solomon M., Networks (1984) |
| [20] | Solomon M., Vehicle Routing and Scheduling with Time Window Constraints Models and Algorithms (1984) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
