Vi studerar graf multicoloring problem, motiverade av schemaläggning av beroende jobb på flera maskiner. I multicoloring problem, hörn har längder som bestämmer antalet färger de måste få, och den önskade färgläggningen kan vara antingen sammanhängande (icke-förebyggande schema) eller godtycklig (förebyggande schema). Vi anser att både summan-av-kompletion gånger mäter, eller summan av den sista färgen tilldelas varje vertex, liksom de mer vanliga makespan mått, eller antalet färger som används. I denna uppsats studerar vi två grundläggande klasser av grafer: plana grafer och partiella k-träd. För båda klasserna, vi ger en polynom tid approximation system (PTAS) för multicoloring summan, för både förebyggande och icke förebyggande fall. Å andra sidan visar vi problemet att vara starkt NP-hård på planar grafer, även i det oviktade fallet, känd som Sum Coloring problem. För icke-förebyggande flerfärgning summan av partiella k-träd, vi få en helt polynom tid approximation schema. Detta är baserat på en pseudo-polynom tid algoritm som innehar för en allmän klass av kostnadsfunktioner. Slutligen ger vi en PTAS för makepan av en förebyggande flerfärgning av partiella k-träd som använder endast O(log n) preemptions. Dessa resultat är baserade på flera egenskaper hos multicolorings och verktyg för att manipulera dem, som kan vara av mer allmän tillämplighet. * Preliminär version finns i APTROX '99 [HK99].
Halldórsson och Kortsarz REF har generaliserat några av resultaten av detta papper till klassen av partiella k-träd (eller grafer av avgränsad trädbredd).
Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees
{'venue': None, 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}