...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >ON COMPUTING THE FREQUENCIES OF INDUCED SUBHYPERGRAPHS
【24h】

ON COMPUTING THE FREQUENCIES OF INDUCED SUBHYPERGRAPHS

机译：关于归纳超图的频率计算

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

摘要

Let F be an r-uniform hypergraph with / vertices, where / > r ≥3. In [Inform. Process. Lett., 99 (2006), pp. 130-134], Yuster posed the problem of whether there exists an algorithm which, for a given r-uniform hypergraph H with n vertices, computes the number of induced copies of F in H in time o(n~f). The analogous question for graphs (r = 2) was known to hold from an O{n~f-ε) time algorithm of Nesetril and Poljak [Comment. Math. Univ. Carolin., 26 (1985), pp. 415-419] (for a constant ε = ε_f > 0 which is independent of n). Here, we present an algorithm for this problem, when r ≥ 3, with running time O(n~f / log_2~n).
机译：令F为具有/顶点的r一致超图，其中/> r≥3。在[通知。处理。 [Lett。，99（2006），pp。130-134]，Yuster提出了以下问题：对于给定的具有n个顶点的r均匀超图H，是否存在一种算法，可以计算H中H的F的诱导副本数。时间o（n〜f）。根据Nesetril和Poljak的O（n〜f-ε）时间算法，已知图的类似问题（r = 2）。数学。大学Carolin。，26（1985），第415-419页]（对于常数ε=ε_f> 0，它与n无关）。在这里，我们提出一个针对该问题的算法，当r≥3时，运行时间为O（n〜f / log_2〜n）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号