咨询与建议

限定检索结果

文献类型

  • 8 篇 期刊文献
  • 4 篇 会议

馆藏范围

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

日期分布

学科分类号

  • 10 篇 工学
    • 9 篇 计算机科学与技术...
    • 2 篇 软件工程
  • 7 篇 理学
    • 7 篇 数学
  • 1 篇 教育学
    • 1 篇 心理学(可授教育学...
  • 1 篇 医学
    • 1 篇 基础医学(可授医学...

主题

  • 12 篇 parameterized co...
  • 2 篇 counting problem...
  • 2 篇 graph homomorphi...
  • 2 篇 fixed-parameter ...
  • 2 篇 bayesian network...
  • 1 篇 multiparametric ...
  • 1 篇 rigid tree autom...
  • 1 篇 approximation al...
  • 1 篇 np-hard
  • 1 篇 randomized compu...
  • 1 篇 finite variable ...
  • 1 篇 multi parameteri...
  • 1 篇 matroid lattices
  • 1 篇 random complexit...
  • 1 篇 algorithms
  • 1 篇 first order logi...
  • 1 篇 inference
  • 1 篇 descriptive comp...
  • 1 篇 parameterized co...
  • 1 篇 approximation

机构

  • 2 篇 univ oxford mert...
  • 1 篇 univ wroclaw ins...
  • 1 篇 radboud univ nij...
  • 1 篇 tu wien austria
  • 1 篇 univ freiburg ab...
  • 1 篇 radboud univ nij...
  • 1 篇 univ ind santand...
  • 1 篇 saarland informa...
  • 1 篇 johannes kepler ...
  • 1 篇 humboldt univ in...
  • 1 篇 univ victoria sc...
  • 1 篇 univ vienna kurt...
  • 1 篇 cluster excellen...
  • 1 篇 tech univ dresde...
  • 1 篇 humboldt univ d-...
  • 1 篇 max planck inst ...
  • 1 篇 rhein westfal th...
  • 1 篇 univ utrecht dep...
  • 1 篇 albert ludwigs u...
  • 1 篇 radboud univ nij...

作者

  • 3 篇 grohe martin
  • 2 篇 donselaar nils
  • 2 篇 kwisthout johan
  • 2 篇 roth marc
  • 1 篇 charatonik witol...
  • 1 篇 andres montoya j...
  • 1 篇 flum jorg
  • 1 篇 woltran stefan
  • 1 篇 mueller moritz
  • 1 篇 weyer mark
  • 1 篇 bodlaender hans ...
  • 1 篇 grueber magdalen...
  • 1 篇 downey rod
  • 1 篇 flum joerg
  • 1 篇 wellnitz philip
  • 1 篇 berkholz christo...
  • 1 篇 chorowska agata
  • 1 篇 van rooij iris
  • 1 篇 fichte johannes ...
  • 1 篇 kronegger martin

语言

  • 11 篇 英文
  • 1 篇 其他
检索条件"主题词=Parameterized complexity theory"
12 条 记 录,以下是1-10 订阅
排序:
Counting and Finding Homomorphisms is Universal for parameterized complexity theory  31
Counting and Finding Homomorphisms is Universal for Paramete...
收藏 引用
31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
作者: Roth, Marc Wellnitz, Philip Univ Oxford Merton Coll Oxford England Cluster Excellence MMCI Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus SIC Saarbrucken Germany
Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where both graphs H and G stem from given classes of g... 详细信息
来源: 评论
Bridging the gap between theory and practice of approximate Bayesian inference
收藏 引用
COGNITIVE SYSTEMS RESEARCH 2013年 24卷 2-8页
作者: Kwisthout, Johan van Rooij, Iris Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav NL-6525 HR Nijmegen Netherlands
In computational cognitive science, many cognitive processes seem to be successfully modeled as Bayesian computations. Yet, many such Bayesian computations have been proven to be computationally intractable (NP-hard) ... 详细信息
来源: 评论
parameterized Random complexity
收藏 引用
theory OF COMPUTING SYSTEMS 2013年 第2期52卷 221-270页
作者: Andres Montoya, Juan Mueller, Moritz Univ Ind Santander Escuela Matemat Bucaramanga Colombia Univ Vienna Kurt Godel Res Ctr Vienna Austria
The classes W[P] and W[1] are parameterized analogues of NP in that they can be characterized by machines with restricted existential nondeterminism. These machine characterizations give rise to two natural notions of... 详细信息
来源: 评论
parameterized complexity of basic decision problems for tree automata
收藏 引用
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2013年 第6期90卷 1150-1170页
作者: Charatonik, Witold Chorowska, Agata Univ Wroclaw Inst Comp Sci PL-50383 Wroclaw Poland Univ Wroclaw Math Inst PL-50384 Wroclaw Poland
There are many decision problems in automata theory (including membership, emptiness, inclusion and universality problems) that are NP-hard for some classes of tree automata (TA). The study of their parameterized comp... 详细信息
来源: 评论
parameterized Counting of Partially Injective Homomorphisms
收藏 引用
ALGORITHMICA 2021年 第6期83卷 1829-1860页
作者: Roth, Marc Saarland Informat Campus SIC Cluster Excellence MMCI Saarbrucken Germany Univ Oxford Merton Coll Oxford England
We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorph... 详细信息
来源: 评论
A multiparametric view on answer set programming
收藏 引用
ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2019年 第1-3期86卷 121-147页
作者: Fichte, Johannes K. Kronegger, Martin Woltran, Stefan Tech Univ Dresden Dresden Germany Johannes Kepler Univ Linz Linz Austria TU Wien Vienna Austria
Disjunctive answer set programming (ASP) is an important framework for declarative modeling and problem solving, where the computational complexity of basic decision problems like consistency (deciding whether a progr... 详细信息
来源: 评论
Bounded fixed-parameter tractability and reducibility
收藏 引用
ANNALS OF PURE AND APPLIED LOGIC 2007年 第1-3期148卷 1-19页
作者: Downey, Rod Flum, Joerg Grohe, Martin Weyer, Mark Humboldt Univ D-10099 Berlin Germany Univ Victoria Sch Math Stat & Comp Sci Wellington New Zealand Univ Freiburg Abt Math Logik D-79104 Freiburg Germany
We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family F. For every family ... 详细信息
来源: 评论
Probabilistic parameterized Polynomial Time  1
收藏 引用
45th International Conference on Current Trends in theory and Practice of Computer Science (SOFSEM)
作者: Donselaar, Nils Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Montessorilaan 3 NL-6525 HR Nijmegen Netherlands
We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout... 详细信息
来源: 评论
parameterized approximability of the disjoint cycle problem
Parameterized approximability of the disjoint cycle problem
收藏 引用
34th International Colloquium on Automata, Languages and Programming
作者: Grohe, Martin Grueber, Magdalena Humboldt Univ Inst Informat Unter Linden 6 D-10099 Berlin Germany
We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph G with n vertices and a positive integer k, the algorithm constructs a family of at least k/p(k) disjoint c... 详细信息
来源: 评论
parameterized Completeness Results for Bayesian Inference  11
Parameterized Completeness Results for Bayesian Inference
收藏 引用
International Conference on Probabilistic Graphical Models
作者: Bodlaender, Hans L. Donselaar, Nils Kwisthout, Johan Univ Utrecht Dept Informat & Comp Sci Princetonpl 5 NL-3508 TB Utrecht Netherlands Radboud Univ Nijmegen Donders Inst Brain Cognit & Behav Thomas van Aquinostr 4 NL-6525 GD Nijmegen Netherlands
We present completeness results for inference in Bayesian networks with respect to two different parameterizations, namely the number of variables and the topological vertex separation number. For this we introduce th... 详细信息
来源: 评论