Vi får en uppsättning V av autonoma agenter (t.ex. datorer i ett distribuerat system) som är anslutna till varandra genom en graf G = (V, E) (t.ex. genom ett kommunikationsnät som förbinder agenterna). Anta att alla agenter har ett unikt ID mellan 1 och N för en parameter N ≥  på V och att varje agent vet sitt ID samt ID för sina grannar i G. Baserat på denna begränsade information, varje agent v måste självständigt beräkna en uppsättning färger Sv  på ett sådant sätt att färgen sätter Su och Sv av angränsande agenter u och v är åtskilda. Vi bevisar att det finns en deterministisk algoritm som använder en total av  och 2 log(N ) / ε 2 ) färger sådan att för varje nod v av G (dvs., för varje agent), vi har  till och med en maximal grad av G. För N =  och 2 log  för),  och 2 + log log N ) färger är nödvändiga även för att tilldela minst en färg till varje nod (dvs, för att beräkna en standard vertex färgning). Med hjälp av randomisering är det möjligt att tilldela en (1 − ε)/(δ + 1)-fraktion av alla färger till varje nod av grad δ med hjälp av endast O( ska logga  och V) färger w.h.p. Vi visar att detta är asymptotiskt nästan optimalt. För grafer med maximal grad krävs färgerna i förväntan, även för att beräkna en giltig färg. Det beskrivna flerfärgsproblemet har direkta tillämpningar i samband med trådlösa ad hoc- och sensornätverk. För att samordna tillgången till det delade trådlösa mediet måste noderna i ett sådant nätverk använda sig av vissa protokoll för medelhög åtkomstkontroll (MAC). Typiska MAC-protokoll styr åtkomsten till den delade kanalen genom tid (TDMA), frekvens (FDMA), eller koddelning flera åtkomstsystem (CDMA) system. Många kanalåtkomstsystem tilldelar en fast uppsättning av tidsslots, frekvenser, eller (ortogonala) koder till noderna i ett nätverk så att noder som stör varandra får separata uppsättningar av tidsslots, frekvenser, eller koduppsättningar. Att hitta en giltig tilldelning av tidsfack, frekvenser eller koder motsvarar därför direkt att beräkna en flerfärgning av en graf G. Bristen på bandbredd, energi och datorresurser i ad hoc- och sensornätverk, liksom den ofta mycket dynamiska karaktären av dessa nätverk kräver att multicoloring kan beräknas baserat på så lite och så lokal information som möjligt.
Intressant i samband med TDMA-system för trådlösa nätverk kan vara REF där det visas hur man beräknar en färg där varje nod med grad d får en 1(d)-fraktion av färgerna i en enda kommunikationsrunda (dvs noder behöver bara lära sig identifiera alla grannar).
Local multicoloring algorithms: Computing a nearly-optimal tdma schedule in constant time
{'venue': 'In STACS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}