Součet zbarvení - Sum coloring - Wikipedia

Součet zbarvení stromu. Součet štítků je 11, menší, než by bylo možné dosáhnout pouze pomocí dvou štítků.

v teorie grafů, a součet zbarvení grafu je označení jeho vrcholů kladnými celými čísly, přičemž žádné dva sousední vrcholy nemají stejné štítky, což minimalizuje součet štítků. Minimální částka, které lze dosáhnout, se nazývá chromatický součet grafu.[1] Chromatické součty a součet zbarvení byly zavedeny Supowitem v roce 1987 pomocí non-graf-teoretické terminologie,[2] a nejprve studoval v teorii grafů pomocí Ewa Kubická (nezávisle na Supowit) ve své disertační práci z roku 1989.[3]

Získání chromatického součtu může vyžadovat použití více odlišných značek než chromatické číslo grafu, a dokonce i když chromatické číslo grafu je omezen, počet odlišných značek potřebných k získání optimálního chromatického součtu může být libovolně velký.[4]

Výpočet chromatického součtu je NP-tvrdé. Může však být vypočítán v lineární čas pro stromy a pseudostromy,[5][6] a v polynomiální čas pro vnější rovinné grafy.[6] Existuje konstantní faktor aproximační algoritmus pro intervalové grafy a pro bipartitní grafy.[7][8] Případ intervalového grafu zůstává NP-tvrdý.[9] Je tomu tak v případě původní žádosti společnosti Supowit v VLSI design a má také aplikace v plánování.[7]

Reference

  1. ^ Małafiejski, Michał (2004), „Sumární vybarvení grafů“, Kubale, Marek (ed.), Barvení grafů, Současná matematika, 352„Providence, RI: American Mathematical Society, s. 55–65, doi:10.1090 / conm / 352/06372, ISBN  9780821834589, PAN  2076989
  2. ^ Supowit, K. J. (1987), "Nalezení maximální rovinné podmnožiny sady sítí v kanálu", Transakce IEEE na počítačově podporovaném návrhu integrovaných obvodů a systémů, 6 (1): 93–94, doi:10.1109 / tcad.1987.1270250
  3. ^ Kubická, Ewa Maria (1989), Chromatický součet a efektivní algoritmy stromu, Ph.D. diplomová práce, Western Michigan University, PAN  2637573
  4. ^ Erdős, Paul; Kubická, Ewa; Schwenk, Allen J. (1990), „Grafy, které vyžadují mnoho barev, aby se dosáhlo jejich chromatického součtu“, Sborník dvacáté jihovýchodní konference o kombinatorice, teorii grafů a výpočtech (Boca Raton, FL, 1989), Congressus Numerantium, 71: 17–28, PAN  1041612
  5. ^ Kubická, Ewa; Schwenk, Allen J. (1989), „Úvod do chromatických součtů“, Sborník ze 17. konference ACM o informatice (CSC '89), New York, NY, USA: ACM, s. 39–45, doi:10.1145/75427.75430, ISBN  978-0-89791-299-0
  6. ^ A b Kubicka, Ewa M. (2005), "Polynomiální algoritmus pro nalezení chromatické sumy pro jednicyklické a vnější rovinné grafy", Ars Combinatoria, 76: 193–201, PAN  2152758
  7. ^ A b Halldórsson, Magnús M .; Kortsarz, Guy; Shachnai, Hadas (2001), „Minimalizace průměrného dokončení specializovaných úkolů a intervalových grafů“, Aproximace, randomizace a kombinatorická optimalizace (Berkeley, CA, 2001), Přednášky v informatice, 2129, Berlín: Springer, s. 114–126, doi:10.1007/3-540-44666-4_15, ISBN  978-3-540-42470-3, PAN  1910356
  8. ^ Giaro, Krzysztof; Janczewski, Robert; Kubale, Marek; Małafiejski, Michał (2002), „Algoritmus přiblížení 27/26 pro zbarvení chromatického součtu bipartitních grafů“, Aproximační algoritmy pro kombinatorickou optimalizaci, Přednášky v informatice, 2462, Berlín: Springer, str. 135–145, doi:10.1007/3-540-45753-4_13, ISBN  978-3-540-44186-1, PAN  2091822
  9. ^ Marx, Dániel (2005), „Krátký důkaz NP-úplnosti zbarvení minimálního součtu intervalů“, Dopisy o operačním výzkumu, 33 (4): 382–384, CiteSeerX  10.1.1.5.2707, doi:10.1016 / j.orl.2004.07.006, PAN  2127409