Petra Šparl (Avtor), Rafał Witkowski (Avtor), Janez Žerovnik (Avtor)

Povzetek

Given a graph ▫$G$▫ and ▫$p \in \mathbb{N}$▫, a proper ▫$n-[p]$▫coloring is a mapping ▫$f \colon V(G) \to 2^{\{1,dots,n\}}$▫ such that ▫$|f(v)| = p$▫ for any vertex ▫$v \in V(G)$▫ and ▫$f(v) \cap f(u) = \emptyset$▫ for any pair of adjacent vertices ▫$u$▫ and ▫$v$▫. An ▫$n-[p]$▫coloring is a special case of a multicoloring. Finding a multicoloring of induced subgraphs of the triangular lattice (called hexagonal graphs) has important applications in cellular networks. In this article we provide an algorithm to find a ▫$7-[3]$▫coloring of triangle-freehexagonal graphs in linear time, without using the four-color theorem, which solves the open problem stated by Sau, Šparl and Žerovnik (2011) and improves the result of Sudeep and Vishwanathan (2005), who proved the existence of a ▫$14-[6]$▫coloring.

Ključne besede

aproksimacijski algoritem;večbarvanje;dodeljevanje frekvenc;heksagonalen graf;approximation algorithm;multicoloring;frequency planning;hexagonal graph;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FS - Fakulteta za strojništvo
UDK: 519.174
COBISS: 7018003 Povezava se bo odprla v novem oknu
ISSN: 0020-0190
Št. ogledov: 1214
Št. prenosov: 100
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarne ključne besede: aproksimacijski algoritem;večbarvanje;dodeljevanje frekvenc;heksagonalen graf;
URN: URN:SI:UM:
Strani: str. 567-571
Letnik: ǂVol. ǂ112
Zvezek: ǂiss. ǂ14-15
Čas izdaje: 2012
ID: 8723553