Abstract
In portable multimedia systems a number of communicating tasks has to be performed on a set of heterogeneous processors in an energy-efficient way. We model this problem 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 differences, 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 efficient) algorithm for general graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. 4OR 1(4), 261–317 (2003)
Bodlaender: A tourist guide through treewidth. Acta Cybernetica 11, 1–21 (1993)
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM Journal on Computing 23(4), 864–894 (1994)
Fernández-Baca, D.: Allocating modules to processors in a distributed system. IEEE Transactions on Software Engineering 15(11), 1427–1436 (1989)
Garey, M.R., Johnson, D.S.: Computers and Intractability. W. H. Freeman and Co., New York (1979)
Hassin, R., Levin, A.: The minimum generalized vertex cover problem. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol. 2832, pp. 289–300. Springer, Heidelberg (2003)
Smit, G.J.M., Havinga, P., Smit, L.T., Heysters, P.M., Rosien, M.A.J.: Dynamic reconfiguration in mobile systems. In: Glesner, M., Zipf, P., Renovell, M. (eds.) FPL 2002. LNCS, vol. 2438, pp. 171–181. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Broersma, H.J., Paulusma, D., Smit, G.J.M., Vlaardingerbroek, F., Woeginger, G.J. (2004). The Computational Complexity of the Minimum Weight Processor Assignment Problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds) Graph-Theoretic Concepts in Computer Science. WG 2004. Lecture Notes in Computer Science, vol 3353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30559-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-30559-0_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24132-4
Online ISBN: 978-3-540-30559-0
eBook Packages: Computer ScienceComputer Science (R0)