The Minimum Spanning Tree Problem with Time Window Constraints

DOI10.1080/01966324.1986.10737201MaRDI QIDQ3773692zbMATH OpenOpenAlexWikidataFDO

Authors Marius M. Solomon

Publication date 1986

Published in American Journal of Mathematical and Management Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/01966324.1986.10737201

zbMATH Keywords

computational complexitycomputational performancegreedyheuristic algorithmsinsertionNP-hardspanning treetime window constraints

Mathematics Subject Classification ID

Trees (05C05) Differentiable maps on manifolds (58C25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A multiperiod degree constrained minimal spanning tree problem
• A constrained minimum spanning tree problem
• The Minimum Spanning Tree Constraint
• On the simultaneous minimum spanning trees problem
• The minimum weight spanning tree with constraints
• The constrained minimum spanning tree problem
• The Minimum Moving Spanning Tree Problem
• The minimum moving spanning tree problem
• The minimum spanning tree problem with conflict constraints and its variations
• Polynomial time approximation schemes for the constrained minimum spanning tree problem

Cites work

• A note on two problems in connexion with graphs
• Computing capacitated minimal spanning trees efficiently
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Formulations and Algorithms for the Capacitated Minimal Directed Tree Problem
• scientific article; zbMATH DE number 3621663 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Implementing vehicle routing algorithms
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimum branchings
• The Capacitated Minimum Spanning Tree
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Topological design of centralized computer networks—formulations and algorithms

Cited in

(4)

• A constrained minimum spanning tree problem
• Stochastically Minimizing Total Penalty Costs in the Two-Machine Flow Shop with Random Processing Times
• A Note on the Complexity of a Simple Transportation Problem
• The minimum spanning tree problem with non-terminal set

This page was built for publication: The Minimum Spanning Tree Problem with Time Window Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3773692)