Paper Info
Title
Optimum schedule problems in store and forward networks
Abstract
Store and forward networks are a convenient model to represent problems in the areas of message communication and traffic control. The goal of a typical scheduling problem is to devise an optimal strategy to send messages from their source sites into their sink ones following paths in the network. In this paper the computational complexity of such a problem is analyzed in the cases of fixed and dynamically variable paths. Unfortunately, it turns out that both of the versions of the considered problem are NP-complete even under very restrictive hypothesis. Moreover, they are not approximable, that is, they can be solved only by polynomial-time heuristic algorithms such that the distance between the exact and the approximate solution is not bounded by any fixed value
Year
DOI
Venue
1994
10.1109/INFCOM.1994.337560
International Journal of Foundations of Computer Science
Keywords
Field
DocType
approximation theory,computational complexity,message switching,optimisation,scheduling,telecommunication traffic,np-complete problem,dynamically variable paths,fixed paths,message communication,optimum schedule problems,polynomial-time heuristic algorithms,store and forward networks,traffic control,scheduling problem
Discrete mathematics,Store and forward,Combinatorics,Mathematical optimization,Job shop scheduling,Network topology,Time complexity,Mathematics,Computational complexity theory
Conference
Volume
Issue
ISSN
6
2
0743-166X
Citations 
PageRank 
References 
2
0.38
6
Authors
2
Name
Order
Citations
PageRank
Andrea E. F. Clementi1116885.30
Miriam di Ianni214417.27