The Minimum Spanning Tree Problem with Time Window Constraints

SYNOPTIC ABSTRACT

This paper is concerned with the computational complexity and the design and analysis of algorithms for the minimum spanning tree problem with time window constraints; such constraints alter the computational complexity of even “easy” problems involving routing components. It is shown that the minimum spanning tree problem with time windows is NP-hard. We then develop O(n²) greedy and insertion approximate algorithms for its solution. Finally, we report our computational experience with these algorithms; this experience indicates that the insertion heuristic had much better performance than the greedy.

Key Words and Phrases:

• minimum spanning tree
• time window constraints
• computational complexity
• heuristics
• computational performance