• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Graph-theoretic concepts in computer science >A New Intersection Model and Improved Algorithms for Tolerance Graphs
【24h】

A New Intersection Model and Improved Algorithms for Tolerance Graphs

机译：公差图的新交集模型和改进算法

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

摘要

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [9], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal (O)(nlogn) algorithms for computing a minimum coloring and a maximum clique, and an (O)(n2) algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times (O)(n2) and (O)(n3) for these problems, respectively.
机译：公差图以这种方式建模间隔关系，即间隔可以容忍一定程度的重叠而不会发生冲突。自从在[9]中引入以来，这类以自然方式概括间隔图和置换图的图吸引了许多研究工作，因为它发现了在基于约束的时间推理，资源分配和调度问题中的许多重要应用，其中。在本文中，我们提出了由三维平行六面体给出的第一个普通公差图的非平凡相交模型，该模型扩展了表征有界公差图类的平面中的平行四边形的相交模型。除了本身很重要之外，这种新的表示形式还使我们能够改善公差图上三个问题的时间复杂度。也就是说，我们提出了用于计算最小着色和最大集团的最佳（O）（nlogn）算法，以及用于计算具有n个顶点的公差图中的最大权重独立集的（O）（n2）算法，从而提高了最佳这些问题的已知运行时间（O）（n2）和（O）（n3）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号