The computational complexity of the minimum weight processor assignment problem

Broersma, H.J. and Paulusma, D. and Smit, G.J.M. and Vlaardingerbroek, F. and Woeginger, G.J. (2005) The computational complexity of the minimum weight processor assignment problem. In: 30th International Workshop on Graph-Theoretic Concepts in Computer Science, June 21-23, 2004, Bad Honnef, Germany.

Preview

PDF
153Kb

Abstract:	In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors. This should be donein an energy-effcient way. We give the background of the problem and model it as a graph optimization problem, which we call the minimum weight processor assignment problem. We show that our setting generalizes several problems known in literature, including minimum multiway cut, graph k-colorability, and minimum (generalized) vertex covering. We show that the minimum weight processor assignment problem is NP-hard, even when restricted to instances where the (process) graph is a bipartite graph with maximum degree at most 3, or with only two processors, or with arbitrarily small weight di erences, or with only two different edge weights. For graphs with maximum degree at most 2 (or in fact the larger class of degree-2-contractible graphs) we give a polynomial time algorithm. Finally we generalize this algorithm into an exact (but not effcient) algorithm for general graphs..
Item Type:	Conference or Workshop Item
Copyright:	© 2005 Springer Verlag
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP) Computer Architecture for Embedded Systems (CAES)
Link to this item:	http://purl.utwente.nl/publications/48397
Official URL:	http://dx.doi.org/10.1007/b104584
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 219813