Conflict-Free Coloring and its Applications
Conflict-Free Coloring and its Applications
复制标题
DOI：
10.1007/978-3-642-41498-5_12
复制
发表时间：
2010-05
期刊：
影响因子：
--
通讯作者：
Shakhar Smorodinsky
中科院分区：
文献类型：
--
作者：
Shakhar Smorodinsky
设H =（V，E）是一个超图. His的无冲突着色是对V的颜色赋值，使得在每个超顶点∈E中，至少有一个颜色相同的顶点。这个概念是经典图着色的一个推广。这样的着色出现在蜂窝天线的频率分配的上下文中，在传感器网络的电池消耗方面，在RFID协议和其他几个领域中。最近的研究论文中，自由着色一直是关注的焦点。在本文中，我们调查这个概念及其组合和算法方面。
LetH= (V, E) be a hypergraph. Aconflict-freecoloring ofHis an assignment of colors toVsuch that, in each hyperedgee∈E, there is at least one uniquely-colored vertex. This notion is an extension of the classical graph coloring. Such colorings arise in the context of frequency assignment to cellular antennae, in battery consumption aspects of sensor networks, in RFID protocols, and several other fields. Conflict-free coloring has been the focus of many recent research papers. In this paper, we survey this notion and its combinatorial and algorithmic aspects.