咨询与建议

限定检索结果

文献类型

  • 2 篇 期刊文献
  • 1 篇 会议

馆藏范围

  • 3 篇 电子文献
  • 0 种 纸本馆藏

日期分布

学科分类号

  • 2 篇 理学
    • 2 篇 数学
  • 2 篇 工学
    • 2 篇 计算机科学与技术...

主题

  • 3 篇 output-polynomia...
  • 2 篇 limited nondeter...
  • 2 篇 dualization
  • 2 篇 combinatorial en...
  • 2 篇 hypergraphs
  • 1 篇 triangle-free gr...
  • 1 篇 hypergraph acycl...
  • 1 篇 enumeration algo...
  • 1 篇 split graphs
  • 1 篇 set coverings
  • 1 篇 independent sets
  • 1 篇 transversal comp...
  • 1 篇 transversals
  • 1 篇 monotone boolean...
  • 1 篇 hitting sets
  • 1 篇 minimal dominati...
  • 1 篇 quasi-polynomial...
  • 1 篇 self-duality
  • 1 篇 treewidth
  • 1 篇 polynomial-total...

机构

  • 1 篇 vienna tech univ...
  • 1 篇 univ bordeaux cn...
  • 1 篇 vienna univ tech...
  • 1 篇 univ oxford comp...
  • 1 篇 univ tokyo grad ...
  • 1 篇 tech univ berlin...
  • 1 篇 univ claude bern...
  • 1 篇 osaka univ div s...
  • 1 篇 univ clermont au...

作者

  • 1 篇 defrain oscar
  • 1 篇 heinrich marc
  • 1 篇 eiter t
  • 1 篇 eiter thomas
  • 1 篇 gottlob g
  • 1 篇 raymond jean-flo...
  • 1 篇 gottlob georg
  • 1 篇 makino k
  • 1 篇 bonamy marthe
  • 1 篇 makino kazuhisa

语言

  • 2 篇 英文
  • 1 篇 其他
检索条件"主题词=output-polynomial algorithms"
3 条 记 录,以下是1-10 订阅
Enumerating Minimal Dominating Sets in Triangle-Free Graphs  36
Enumerating Minimal Dominating Sets in Triangle-Free Graphs
收藏 引用
36th International Symposium on Theoretical Aspects of Computer Science (STACS)
作者: Bonamy, Marthe Defrain, Oscar Heinrich, Marc Raymond, Jean-Florent Univ Bordeaux CNRS Bordeaux France Univ Clermont Auvergne LIMOS Clermont Ferrand France Univ Claude Bernard LIRIS Lyon France Tech Univ Berlin LaS Team Berlin Germany
It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this paper we prove that this is the case in triangle-free graphs. This answers a quest... 详细信息
来源: 评论
Computational aspects of monotone dualization: A brief survey
收藏 引用
DISCRETE APPLIED MATHEMATICS 2008年 第11期156卷 2035-2049页
作者: Eiter, Thomas Makino, Kazuhisa Gottlob, Georg Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria Univ Tokyo Grad Sch Informat & Technol Dept Math & Informat Tokyo 1138656 Japan Univ Oxford Comp Lab Oxford OX1 3QD England
Dualization of a monotone Boolean function represented by a conjunctive normal form (CNF) is a problem which, in different disguise, is ubiquitous in many areas including Computer Science, Artificial Intelligence, and... 详细信息
来源: 评论
New results on monotone dualization and generating hypergraph transversals
收藏 引用
SIAM JOURNAL ON COMPUTING 2003年 第2期32卷 514-537页
作者: Eiter, T Gottlob, G Makino, K Vienna Tech Univ Inst Informat Syst A-1040 Vienna Austria Osaka Univ Div Syst Sci Grad Sch Engn Sci Osaka 5608531 Japan
We consider the problem of dualizing a monotone CNF (equivalently, computing all minimal transversals of a hypergraph) whose associated decision problem is a prominent open problem in NP-completeness. We present a num... 详细信息
来源: 评论