b'\n_START_ARTICLE_\nAlgoritmo de Coffman-Graham\n_START_PARAGRAPH_\nEn programaci\xc3\xb3n de taller y trazado de grafos, el algoritmo Coffman-Graham es un proceso de c\xc3\xa1lculo, llamado as\xc3\xad por Edward G. Coffman, Jr. y Ronald Graham, cuyo fin es organizar los elementos de un conjunto parcialmente ordenado en una secuencia de niveles. El algoritmo elige una disposici\xc3\xb3n tal que un elemento que viene despu\xc3\xa9s de otro en el orden se asigna a un nivel inferior, y tal que cada nivel W contiene elementos que no superan una amplitud dada. Cuando W = 2 se utiliza la cantidad m\xc3\xadnima posible de niveles distintos,\xe2\x80\x8b y, en general, se utilizan como m\xc3\xa1ximo 2 \xe2\x88\x92 2/W veces tantos niveles como sea necesario.\xe2\x80\x8b\xe2\x80\x8b\n_START_SECTION_\nAn\xc3\xa1lisis\n_START_PARAGRAPH_\nComo Coffman\xc2\xa0y Graham (1972) prob\xc3\xb3 originalmente, su algoritmo calcula una asignaci\xc3\xb3n \xc3\xb3ptima para W = 2; es decir, para programar problemas con trabajos de longitud unitaria en dos procesadores, o para problemas de dibujo de gr\xc3\xa1ficos en capas con un m\xc3\xa1ximo de dos v\xc3\xa9rtices por capa.\xe2\x80\x8b Un algoritmo estrechamente relacionado tambi\xc3\xa9n encuentra la soluci\xc3\xb3n \xc3\xb3ptima para programar trabajos con longitudes variables, lo que permite la aceleraci\xc3\xb3n de trabajos programados, en dos procesadores.\xe2\x80\x8b Para W > 2, el algoritmo de Coffman-Graham usa una cantidad de niveles (o calcula un programa con un intervalo de trabajo) que est\xc3\xa1 dentro de un factor de 2 \xe2\x88\x92 2/W del \xc3\xb3ptimo.\xe2\x80\x8b\xe2\x80\x8b Por ejemplo, para W = 3, esto significa que utiliza a lo sumo 4/3 veces tantos niveles como sea \xc3\xb3ptimo. Cuando el orden parcial de las restricciones de precedencia es un orden de intervalos, o pertenece a varias clases relacionadas de \xc3\xb3rdenes parciales, el algoritmo de Coffman-Graham encuentra una soluci\xc3\xb3n con el n\xc3\xbamero m\xc3\xadnimo de niveles independientemente de su ancho de banda.\xe2\x80\x8b_NEWLINE_Adem\xc3\xa1s de encontrar horarios con intervalos de trabajo peque\xc3\xb1os, el algoritmo de Coffman-Graham (modificado a partir de la  aqu\xc3\xad mostrada para que ordene topol\xc3\xb3gicamente el grafo inverso de G y coloque los v\xc3\xa9rtices lo m\xc3\xa1s pronto posible en lugar de lo m\xc3\xa1s tarde posible) minimiza el flujo de tiempo total de dos programas de procesador y la suma de los tiempos de finalizaci\xc3\xb3n de los trabajos individuales. Se puede usar un algoritmo relacionado para minimizar el tiempo de flujo total para una versi\xc3\xb3n del problema en la que se permite alterar la precedencia de los trabajos.\xe2\x80\x8b_NEWLINE_Coffman\xc2\xa0y Graham (1972) y Lenstra\xc2\xa0y Rinnooy Kan (1978)\xe2\x80\x8b indican que la complejidad de tiempo del algoritmo de Coffman-Graham, en un orden parcial de elementos n, es O(n\xc2\xb2). Sin embargo, este an\xc3\xa1lisis omite el tiempo para construir la reducci\xc3\xb3n transitiva, que no se sabe que sea posible dentro de este l\xc3\xadmite. Sethi\xc2\xa0(1976) muestra c\xc3\xb3mo implementar la etapa de ordenamiento topol\xc3\xb3gico del algoritmo en tiempo lineal, basado en la idea de refinamiento de partici\xc3\xb3n.\xe2\x80\x8b Sethi tambi\xc3\xa9n muestra c\xc3\xb3mo implementar la etapa de asignaci\xc3\xb3n de nivel del algoritmo de manera eficiente mediante el uso de una estructura de datos para conjuntos disjuntos. En particular, con una versi\xc3\xb3n de esta estructura publicada posteriormente por Gabow\xc2\xa0y Tarjan (1985), esta etapa tambi\xc3\xa9n requiere tiempo lineal.\xe2\x80\x8b'