Hispanopedia Wiki
En teoría de grafos , una coloración por suma de un grafo consiste en etiquetar sus vértices con enteros positivos, sin que dos vértices adyacentes tengan la misma etiqueta, minimizando así la suma de las etiquetas. La suma mínima alcanzable se denomina suma cromática del grafo. [ 1 ] Las sumas cromáticas y la coloración por suma fueron introducidas por Supowit en 1987 utilizando terminología ajena a la teoría de grafos, [ 2 ] y estudiadas por primera vez en términos de teoría de grafos por Ewa Kubicka (independientemente de Supowit) en su tesis doctoral de 1989. [ 3 ]
La obtención de la suma cromática puede requerir el uso de más etiquetas distintas que el número cromático del grafo, e incluso cuando el número cromático de un grafo está acotado, el número de etiquetas distintas necesarias para obtener la suma cromática óptima puede ser arbitrariamente grande. [ 4 ]
El cálculo de la suma cromática es NP-difícil . Sin embargo, puede calcularse en tiempo lineal para árboles y pseudoárboles , [ 5 ] [ 6 ] y en tiempo polinomial para grafos exteriores planares . [ 6 ] Existe un algoritmo de aproximación de factor constante para grafos de intervalos y para grafos bipartitos . [ 7 ] [ 8 ] El caso de los grafos de intervalos sigue siendo NP-difícil. [ 9 ] Es el caso que surge en la aplicación original de Supowit en el diseño VLSI , y también tiene aplicaciones en la planificación . [ 7 ]
Referencias
- ^ Małafiejski, Michał (2004), "Coloración de sumas de gráficos", en Kubale, Marek (ed.), Graph Colorings , Matemáticas contemporáneas, vol. 352, Providence, RI: Sociedad Matemática Estadounidense, págs. 55 a 65, doi : 10.1090/conm/352/06372 , ISBN 9780821834589, MR 2076989
- ↑ Supowit, KJ (1987), "Finding a maximum planar subset of a set of nets in a channel", IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems , 6 (1): 93– 94, Bibcode : 1987ITCAD...6...93S , doi : 10.1109/tcad.1987.1270250 , S2CID 14949711
- ↑ Kubicka, Ewa Maria (1989), La suma cromática y algoritmos de árboles eficientes , tesis doctoral, Western Michigan University, MR 2637573
- ↑ Erdős, Paul ; Kubicka, Ewa ; Schwenk, Allen J. (1990), "Grafos que requieren muchos colores para alcanzar su suma cromática", Actas de la Vigésima Conferencia del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Ratón, FL, 1989), Congressus Numerantium , 71 : 17–28 , MR 1041612
- ↑ Kubicka, Ewa ; Schwenk, Allen J. (1989), "Una introducción a las sumas cromáticas", Actas de la 17.ª Conferencia de Ciencias de la Computación de la ACM (CSC '89) , Nueva York, NY, EE. UU.: ACM, págs. 39-45 , doi : 10.1145/75427.75430 , ISBN 978-0-89791-299-0, S2CID 28544302
- 1 2 Kubicka, Ewa M. (2005), "Algoritmo polinomial para encontrar la suma cromática para grafos unicíclicos y exteriores planares", Ars Combinatoria , 76 : 193– 201, MR 2152758
- 1 2 Halldórsson, Magnús M.; Kortsarz, Guy; Shachnai, Hadas (2001), "Minimizing average completion of dedicated tasks and interval graphs", Aproximation, randomization, and combinatorial optimization (Berkeley, CA, 2001) , Lecture Notes in Computer Science, vol. 2129, Berlín: Springer, pp. 114–126 , doi : 10.1007/3-540-44666-4_15 , ISBN 978-3-540-42470-3, MR 1910356
- ↑ Giaro, Krzysztof; Janczewski, Robert; Kubale, Marek; Małafiejski, Michał (2002), "Un algoritmo de aproximación 27/26 para la coloración por suma cromática de grafos bipartitos", Algoritmos de aproximación para la optimización combinatoria , Lecture Notes in Computer Science, vol. 2462, Berlín: Springer, pp. 135–145 , doi : 10.1007/3-540-45753-4_13 , ISBN 978-3-540-44186-1, MR 2091822
- ↑ Marx, Dániel (2005), "Una breve demostración de la NP-completitud de la coloración de intervalos de suma mínima", Operations Research Letters , 33 (4): 382–384 , CiteSeerX 10.1.1.5.2707 , doi : 10.1016/j.orl.2004.07.006 , MR 2127409
- Coloreado de gráficos
- problemas NP-completos