Összegszínezés
A matematika, azon belül a gráfelmélet területén egy gráf összegszínezése (sum coloring) a gráf csúcsainak pozitív egész számokkal való címkézése oly módon, hogy a szomszédos csúcsokhoz tartozó címkék nem egyezhetnek meg, a címkék összege pedig minimális legyen. Ezt a minimális összeg a gráf kromatikus összege (chromatic sum).[1] A kromatikus összeg és az összegszínezés bevezetése gráfelméleten kívül eső terminológiával Supowit nevéhez fűződik (1987),[2] gráfelméleti eszközökkel elsőként (Supowittől függetlenül) Ewa Kubicka vizsgálta ezeket a fogalmakat 1989-es doktori disszertációjában.[3]
A kromatikus összeghez szükséges címkék száma meghaladhatja a gráf kromatikus számát, és még ha a kromatikus szám korlátos, az optimális kromatikus összeg eléréséhez szükséges különböző címkék száma tetszőlegesen nagy lehet.[4]
A kromatikus összeg meghatározása NP-nehéz. Fák és pszeudoerdők esetében azonban lineáris időben,[5][6] külsíkgráfoknál pedig polinom időben meghatározható.[6] Intervallumgráfokra és páros gráfokra létezik konstans tényezőjű közelítő algoritmus.[7][8] Ettől még a Supowit eredeti, VLSI-tervezésről szóló cikkében, valamit ütemezési feladatokban[7] szóba jövő intervallumgráf-eset NP-nehéz marad.[9]
Az összegszínezés a csúcsokon kívül alkalmazható az élekre (összeg-élszínezés) valamint a csúcsok és élek uniójára (totális összegszínezés) is.
Fordítás
szerkesztés- Ez a szócikk részben vagy egészben a Sum coloring című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Jegyzetek
szerkesztés- ↑ Małafiejski, Michał (2004), "Sum coloring of graphs", in Kubale, Marek, Graph Colorings, vol. 352, Contemporary Mathematics, Providence, RI: American Mathematical Society, pp. 55–65, DOI 10.1090/conm/352/06372
- ↑ Supowit, K. J. (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, DOI 10.1109/tcad.1987.1270250
- ↑ Kubicka, Ewa Maria (1989), The chromatic sum and efficient tree algorithms, Ph.D. thesis, Western Michigan University
- ↑ Erdős, Pál; Kubicka, Ewa & Schwenk, Allen J. (1990), "Graphs that require many colors to achieve their chromatic sum", Congressus Numerantium 71: 17–28
- ↑ Kubicka, Ewa & Schwenk, Allen J. (1989), "An introduction to chromatic sums", Proceedings of the 17th ACM Computer Science Conference (CSC '89), New York, NY, USA: ACM, pp. 39–45, ISBN 0-89791-299-3, DOI 10.1145/75427.75430
- ↑ a b Kubicka, Ewa M. (2005), "Polynomial algorithm for finding chromatic sum for unicyclic and outerplanar graphs", Ars Combinatoria 76: 193–201
- ↑ a b Halldórsson, Magnús M.; Kortsarz, Guy & Shachnai, Hadas (2001), "Minimizing average completion of dedicated tasks and interval graphs", Approximation, randomization, and combinatorial optimization (Berkeley, CA, 2001), vol. 2129, Lecture Notes in Computer Science, Berlin: Springer, pp. 114–126, DOI 10.1007/3-540-44666-4_15
- ↑ Giaro, Krzysztof; Janczewski, Robert & Kubale, Marek et al. (2002), "A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs", Approximation algorithms for combinatorial optimization, vol. 2462, Lecture Notes in Computer Science, Berlin: Springer, pp. 135–145, DOI 10.1007/3-540-45753-4_13
- ↑ Marx, Dániel (2005), "A short proof of the NP-completeness of minimum sum interval coloring", Operations Research Letters 33 (4): 382–384, DOI 10.1016/j.orl.2004.07.006
