  


On the NPCompleteness of the MultiPeriod Minimum Spanning Tree Problem
Rosklin Chagas(rosklinjulianogmail.com) Abstract: In this note, we consider the Multiperiod Minimum Spanning Tree Problem (MMST), a variant of the well known Minimum Spanning Tree Problem (MST), that consists in the fol lowing. Given a connected and undirected graph G and a finite discrete time horizon, one has to schedule the moment in time edges are added to a solution. For each time period, a partial solution consisting of a tree must be built. Once an edge is added to a tree at a given time, it remains in the solution thereafter. At the end of the planning time, the complete solution must be a spanning tree of G. Vertices must be spanned by these trees at times that do not exceed predefined dates that depend on each vertex. Edges’ costs represent the discounted cash flows of the installation cost at the time of installation plus maintenance costs, from that time until the end of the planning time. The goal is to choose and schedule the installation of the edges, such that the final spanning tree has a minimum cost. The complexity of MMST was not addressed before. We show that, unlike the MST case, the decision version of MMST is N P−Complete. Keywords: Multiperiod spanning trees, Network Optimization Category 1: Combinatorial Optimization (Other ) Category 2: Applications  OR and Management Sciences (Telecommunications ) Category 3: Applications  OR and Management Sciences (Scheduling ) Citation: Technical Report Departamento de Ciência da Computação Universidade Federal de Minas Gerais Download: [PDF] Entry Submitted: 03/29/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  