...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >ON THE POWER OF GRAPH SEARCHING FOR COCOMPARABILITY GRAPHS
【24h】

ON THE POWER OF GRAPH SEARCHING FOR COCOMPARABILITY GRAPHS

机译：关于可比图的图搜索能力

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

摘要

In this paper we study how graph searching on a cocomparability graph G can be used to produce cocomp orderings (i.e., orderings that are linear extensions of some transitive orientation of G) that yield simple algorithms for various intractable problems in general. Such techniques have been used to find a simple certifying algorithm for the minimum path cover problem. In particular we present a characterization of the searches that preserve cocomp orderings when used as a "+" sweep. This allows us to present a toolbox of different graph searches and a framework to solve various problems on cocomparability graphs. We illustrate these techniques by describing a very simple certifying algorithm for the maximum independent set problem as well as a simple permutation graph recognition algorithm.
机译：在本文中，我们研究了如何在可比性图G上进行图搜索来生成cocomp排序（即，是G的某些传递方向的线性扩展的排序），这些排序通常会产生针对各种棘手问题的简单算法。已经使用这种技术来找到用于最小路径覆盖问题的简单证明算法。特别是，我们提供了当用作“ +”扫描时保留cocomp排序的搜索的特征。这使我们能够展示不同图搜索的工具箱和解决可比图上各种问题的框架。我们通过描述用于最大独立集问题的非常简单的证明算法以及简单的置换图识别算法来说明这些技术。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号