Buffer minimization using max-coloring
Sriram V. Pemmaraju, Rajiv Raman, Kasturi Varadarajan · 2004
Given a graph G = (V, E) and positive integral vertex weights w: V → N, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C_1, C_2, ..., C_k, minimize i=1 max v#C i w(v). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general purpose memory management of the operating system. Specifically, companies have tried to solve this problem in the design of memory managers for wireless protocol stacks such as GPRS or 3G. Though this problem seems similar...