Optimization Online


On the NP-Completeness of the Multi-Period Minimum Spanning Tree Problem

Rosklin Chagas(rosklinjuliano***at***gmail.com)
Alexandre Cunha(acunha***at***dcc.ufmg.br)

Abstract: In this note, we consider the Multi-period 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 pre-defined 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: Multi-period 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
Entry Accepted: 03/29/2016
Entry Last Modified: 03/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society