首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:Randomised Enumeration of Small Witnesses Using a Decision Oracle
  • 本地全文:下载
  • 作者:Kitty Meeks
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:63
  • 页码:22:1-22:12
  • DOI:10.4230/LIPIcs.IPEC.2016.22
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Many combinatorial problems involve determining whether a universe of n elements contains a witness consisting of k elements which have some specified property. In this paper we investigate the relationship between the decision and enumeration versions of such problems: efficient methods are known for transforming a decision algorithm into a search procedure that finds a single witness, but even finding a second witness is not so straightforward in general. In this paper we show that, if the decision version of the problem belongs to FPT, there is a randomised algorithm which enumerates all witnesses in time f(k)*poly(n)*N, where N is the total number of witnesses and f is a computable function. This also gives rise to an efficient algorithm to count the total number of witnesses when this number is small.
  • 关键词:enumeration algorithms; parameterized complexity; randomized algorithms; color coding
国家哲学社会科学文献中心版权所有