• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Conflict-free coloring.
【24h】

Conflict-free coloring.

机译：无冲突的着色。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graph and hypergraph colorings constitute an important subject in combinatorics and algorithm theory. In this work, we study conflict-free coloring for hypergraphs. Conflict-free coloring is one possible generalization of traditional graph coloring. Conflict-free coloring hypergraphs induced by geometric shapes, like intervals on the line, or disks on the plane, has applications in frequency assignment in cellular networks. Colors model frequencies and since the frequency spectrum is limited and expensive, the goal of an algorithm is to minimize the number of assigned frequencies, that is, reuse frequencies as much as possible.;We concentrate on an online variation of the problem, especially in the case where the hypergraph is induced by intervals. For deterministic algorithms, we introduce a hierarchy of models ranging from static to online and we compute lower and upper bounds on the numbers of colors used.;In the randomized oblivious adversary model, we introduce a framework for conflict-free coloring a specific class of hypergraphs with a logarithmic number of colors. This specific class includes many hypergraphs arising in geometry and gives online randomized algorithm that use fewer colors and fewer random bits than other algorithms in the literature. Based on the same framework, we initiate the study of online deterministic algorithms that recolor few points.;For the problem of conlict-free coloring points with respect to a given set of intervals, we describe an efficient algorithm that computes a coloring with at most twice the number of colors of an optimal coloring. We also show that there is a family of inputs that force our algorithm to use two times the number of colors of an optimal solution.;Then, we study conflict-free coloring problems in graphs. We compare conflict-free coloring with respect to paths of graphs to a closely related problem, called vertex ranking, or ordered coloring. For conflict-free coloring with respect to neighborhoods of vertices of graphs, we prove that number of colors in the order of the square root of the number of vertices is sufficient and sometimes necessary.;Finally, we initiate the study of Ramsey-type problems for conflict-free colorings and compute a van der Waerden-like number.
机译：图和超图着色是组合和算法理论中的重要主题。在这项工作中，我们研究了超图的无冲突着色。无冲突着色是传统图形着色的一种可能概括。由几何形状（如直线上的间隔或平面上的磁盘）引起的无冲突着色超图，已在蜂窝网络的频率分配中得到应用。对模型频率进行着色，并且由于频谱有限且昂贵，因此算法的目标是最大程度地减少分配的频率，即尽可能多地重复使用频率。；我们专注于问题的在线变化，尤其是在间隔诱发超图的情况。对于确定性算法，我们引入了从静态到在线的模型层次结构，并计算了所使用颜色的数量上限和下限;在随机遗忘的对手模型中，我们引入了为特定类别的对象进行无冲突着色的框架颜色数量为对数的超图。该特定类包括许多出现在几何图形中的超图，并提供了在线随机算法，该算法比文献中的其他算法使用更少的颜色和更少的随机位。基于相同的框架，我们开始研究对少数点进行重新着色的在线确定性算法。针对针对给定间隔的无冲突着色点的问题，我们描述了一种高效的算法，该算法最多可以计算着色次数最佳着色的颜色数量的两倍。我们还表明，有一系列输入迫使我们的算法使用最佳解决方案的两倍颜色;然后，我们研究了图形中的无冲突着色问题。我们将与图路径有关的无冲突着色与一个紧密相关的问题（称为顶点排序或有序着色）进行比较。对于关于图的顶点邻域的无冲突着色，我们证明了按顶点数的平方根顺序排列的颜色数是足够的，有时是必要的。最后，我们开始研究Ramsey型问题用于无冲突的着色并计算类似范德瓦尔登的数。

著录项

  • 作者

    Cheilaris, Panagiotis.;

  • 作者单位

    City University of New York.;

  • 授予单位 City University of New York.;
  • 学科 Computer Science.
  • 学位 Ph.D.
  • 年度 2009
  • 页码 152 p.
  • 总页数 152
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 自动化技术、计算机技术;
  • 关键词

  • 入库时间 2022-08-17 11:37:46

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号