| DEDICATION | 第4-5页 |
| ACKNOWLEDGEMENT | 第5-8页 |
| 1. INTRODUCTION | 第8-15页 |
| 2. FORMULATION AND COMPLEXITY | 第15-28页 |
| 2.1. Formulation of the Quadratic Minimal Spanning Tree Problem (QMST) | 第15-18页 |
| 2.2. Motivation of our Study | 第18-20页 |
| 2.3. NP-Completeness of the QMST | 第20-25页 |
| 2.4. NP-Completeness of the AQMST | 第25-28页 |
| 3. BOUNDING TECHNIQUES FOR THE QMST | 第28-51页 |
| 3.1. Linear Programming Approach | 第28-31页 |
| 3.2. Lagrangean Relaxation Approach | 第31-32页 |
| 3.3. The Decomposition Bound (DB) | 第32-33页 |
| 3.4. The Parametrized Bound (PB) | 第33-38页 |
| 3.5. The Leveling Method for Searching the Best PB | 第38-40页 |
| 3.6. Computational Experiments | 第40-51页 |
| 4. A BOUNDING TECHNIQUE FOR A CLASS OF QUADRATIC 0-1 PROGRAMS | 第51-63页 |
| 4.1. Brief Introduction of the Problem | 第51-52页 |
| 4.2. The Parametrized Lower Bound | 第52-56页 |
| 4.3. A Sufficient Condition for the Best Parameters | 第56-58页 |
| 4.4. Leveling Algorithm and Its Convergence | 第58-63页 |
| 5. ON THE LOWER BOUND OF THE QUADRATIC ASSIGNMENT PROBLEM (QAP) | 第63-81页 |
| 5.1. Existing Bounding Techniques | 第63-71页 |
| 5.2. Application of the Leveling Method to the QAP | 第71-75页 |
| 5.3. Comparisons | 第75-81页 |
| 6. SOLUTION TECHNIQUES FOR THE QMST | 第81-102页 |
| 6.1. General Description | 第81-83页 |
| 6.2. Branch-and-Bound Algorithm Ⅰ (with decomposition bounds) | 第83-85页 |
| 6.3. Branch-and-Bound Algorithm Ⅱ (with parametrized bounds) | 第85-90页 |
| 6.4. Branch-and-Bound Algorithm Ⅲ (for the Adjacent-only QMST) | 第90-93页 |
| 6.5. Heuristic Algorithms | 第93-98页 |
| 6.6. Computational Experiments | 第98-102页 |
| 7. CONCLUSIONS | 第102-106页 |
| APPENDIX A. Network Terminology | 第106-108页 |
| APPENDIX B. Efficient Algorithms for Solving the MST | 第108-110页 |
| APPENDIX C. Formulations of the QAP and the KBP | 第110-112页 |
| APPENDIX D. Test Problems for Section 5.3 | 第112-119页 |
| BIBLIOGRAPHY | 第119-124页 |
