检索结果-内蒙古大学图书馆

您好，读者！请登录

内蒙古大学图书馆

首页
概况
党建
资源
服务
科研支持
- 论文收录引用证明
- 科技查新
知识产权
档案馆
帮助

咨询与建议

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入0个字，您还可以输入200个字

全部搜索
期刊论文
图书
学位论文
标准
纸本馆藏
外文资源发现
数据库导航
超星发现

高级检索

时间限定

出版年份：

文献类型

图书期刊文献学位论文多媒体

馆藏选择

电子馆藏纸本馆藏

核心期刊

全部期刊 SCI 收录期刊 SSCI 收录期刊 EI 收录期刊 CSCD 收录期刊 CSSCI 收录期刊

语言

中文英文

文献类型

期刊文献图书学位论文标准纸本馆藏

帮助

文字说明：

T=题名（书名、题名），A=作者（责任者），K=主题词，P=出版物名称，PU=出版社名称，O=机构（作者单位、学位授予单位、专利申请人），L=中图分类号，C=学科分类号，U=全部字段，Y=年（出版发行年、学位年度、标准发布年）

检索规则说明：

AND代表“并且”；OR代表“或者”；NOT代表“不包含”；(注意必须大写,运算符两边需空一格)

检索范例：

范例一：(K=图书馆学 OR K=情报学) AND A=范并思 AND Y=1982-2016
范例二：P=计算机应用与软件 AND (U=C++ OR U=Basic) NOT K=Visual AND Y=2011-2016

分类表

所选分类

>> <<

限定检索结果

文献类型

821 篇 期刊文献
305 篇 会议
11 篇 学位论文

馆藏范围

1,137 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

943 篇 工学
- 921 篇 计算机科学与技术...
- 236 篇 软件工程
- 40 篇 控制科学与工程
- 32 篇 电气工程
- 6 篇 机械工程
- 6 篇 信息与通信工程
- 2 篇 生物工程
- 1 篇 仪器科学与技术
- 1 篇 电子科学与技术（可...
- 1 篇 建筑学
- 1 篇 土木工程
- 1 篇 测绘科学与技术
- 1 篇 石油与天然气工程
594 篇 理学
- 588 篇 数学
- 9 篇 生物学
- 4 篇 统计学（可授理学、...
- 1 篇 物理学
- 1 篇 化学
105 篇 管理学
- 105 篇 管理科学与工程(可...
- 20 篇 工商管理
20 篇 经济学
- 20 篇 应用经济学
7 篇 法学
- 7 篇 法学
2 篇 文学
- 2 篇 外国语言文学
2 篇 农学
- 1 篇 水产
2 篇 医学
- 1 篇 基础医学(可授医学...
- 1 篇 临床医学
1 篇 哲学
- 1 篇 哲学

主题

1,137 篇 parameterized co...
126 篇 kernelization
98 篇 treewidth
58 篇 computational co...
56 篇 graph algorithms
44 篇 vertex cover
42 篇 algorithms
41 篇 fixed-parameter ...
34 篇 dynamic programm...
27 篇 approximation al...
24 篇 planar graphs
22 篇 fpt
20 篇 exponential time...
20 篇 graph minors
19 篇 theory
19 篇 feedback vertex ...
18 篇 exact algorithms
18 篇 dominating set
18 篇 approximation
17 篇 fixed parameter ...

机构

46 篇 ben gurion univ ...
42 篇 univ bergen berg...
39 篇 univ bergen dept...
38 篇 inst math sci ma...
35 篇 univ bergen dept...
30 篇 hbni inst math s...
20 篇 tu wien algorith...
17 篇 ben gurion univ ...
17 篇 tu berlin inst s...
16 篇 univ montpellier...
14 篇 univ montpellier...
12 篇 tu wien austria
12 篇 univ utrecht utr...
12 篇 univ durham sch ...
12 篇 univ tubingen wi...
11 篇 hbni inst math s...
11 篇 inst math sci ch...
10 篇 max planck inst ...
10 篇 univ calif santa...
10 篇 depaul univ sch ...

作者

93 篇 saurabh saket
59 篇 sau ignasi
47 篇 golovach petr a.
46 篇 lokshtanov danie...
43 篇 zehavi meirav
40 篇 fomin fedor v.
39 篇 niedermeier rolf
35 篇 szeider stefan
32 篇 kratsch stefan
31 篇 ganian robert
29 篇 thilikos dimitri...
26 篇 raman venkatesh
23 篇 ordyniak sebasti...
23 篇 tsur dekel
22 篇 hermelin danny
20 篇 marx daniel
18 篇 panolan fahad
18 篇 fomin fedor v
18 篇 yang yongjie
17 篇 paul christophe

语言

1,071 篇 英文
63 篇 其他

检索条件"主题词=parameterized complexity"

共 1137 条记录，以下是871-880 订阅

全选清除本页清除全部题录导出标记到"检索档案"

详细简洁

排序：

The Control complexity of r-Approval: from the Single-Peaked Case to the General Case 13

The Control Complexity of r-Approval: from the Single-Peaked...

引用

International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yang, Yongjie Guo, Jiong Univ Saarland Campus E 1-7 D-66123 Saarbrucken Germany

ISBN: (纸本)9781450327381

A natural generalization of the single-peaked elections is the k-peaked elections, where at most k peaks are allowed in each vote. Motivated by NP-hardness in general and polynomial-time solvability in single-peaked elections, we aim at establishing a complexity dichotomy of several control problems for r-approval voting in k-peaked elections with respect to k. It turns out that most NP-completeness results in general also hold in k-peaked elections, even for k = 2;3. On the other hand, we derive polynomial-time algorithms for certain control problems for k = 2. In addition, we also study the problems from the viewpoint of parameterized complexity and achieve both FPT and W-hardness results. Several of our results apply to approval voting and sincere-strategy preference-based approval voting as well.

关键词： single-peaked approval voting control parameterized complexity kernel

来源：评论

学校读者我要写书评

暂无评论

Improved FPT Algorithms for Weighted Independent Set in Bull-Free Graphs 9

Improved FPT Algorithms for Weighted Independent Set in Bull...

引用

9th International Symposium on parameterized and Exact Computation (IPEC)

作者： du Cray, Henri Perret Sau, Ignasi CNRS LIRMM AlGCo Project Team Montpellier France

ISBN: (纸本)9783319135243;9783319135236

Very recently, Thomasse, Trotignon and Vuskovic [WG 2014] have given an FPT algorithm for WEIGHTED INDEPENDENT SET in bull-free graphs parameterized by the weight of the solution, running in time 2(O(k5)).n(9). In this article we improve this running time to 2(O(k2)).n(7). As a byproduct, we also improve the previous Turing-kernel for this problem from O(k(5)) to O(k(2)). Furthermore, for the subclass of bull-free graphs without holes of length at most 2p - 1 for p >= 3, we speed up the running time to 2(O(k.k1/p-1)) . n(7). As p grows, this running time is asymptotically tight in terms of k, since we prove that for each integer p >= 3, WEIGHTED INDEPENDENT SET cannot be solved in time 2(o(k)) . n(O(1)) in the class of {bull, C-4,..., C2p-1}-free graphs unless the ETH fails.

关键词： parameterized complexity FPT algorithm Bull-free graphs Independent set Turing-kernel

来源：评论

学校读者我要写书评

暂无评论

One Hierarchy Spawns Another: Graph Deconstructions and the complexity Classification of Conjunctive Queries 14

One Hierarchy Spawns Another: Graph Deconstructions and the ...

引用

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Chen, Hubie Mueller, Moritz Univ Basque Country Dept LSI E-20018 San Sebastian Spain Basque Fdn Sci IKERBASQUE E-20018 San Sebastian Spain Univ Wien Kurt Godel Res Ctr A-1090 Vienna Austria

ISBN: (纸本)9781450328869

We study the problem of conjunctive query evaluation relative to a class of queries;this problem is formulated here as the relational homomorphism problem relative to a class of structures A, wherein each instance must be a pair of structures such that the first structure is an element of A. We present a comprehensive complexity classification of these problems, which strongly links graph-theoretic properties of A to the complexity of the corresponding homomorphism problem. In particular, we define a binary relation on graph classes and completely describe the resulting hierarchy given by this relation. This binary relation is defined in terms of a notion which we call graph deconstruction and which is a variant of the well-known notion of tree decomposition. We then use this hierarchy of graph classes to infer a complexity hierarchy of homomorphism problems which is comprehensive up to a computationally very weak notion of reduction, namely, a parameterized version of quantifier-free reductions. In doing so, we obtain a significantly refined complexity classification of homomorphism problems, as well as a unifying, modular, and conceptually clean treatment of existing complexity classifications. We then present and develop the theory of Ehrenfeucht-Fraisse-style pebble games which solve the homomorphism problems where the cores of the structures in A have bounded tree depth. Finally, we use our framework to classify the complexity of model checking existential sentences having bounded quantifier rank.

关键词： Conjunctive queries Homomorphisms Graph decompositions parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

Quantified Conjunctive Queries on Partially Ordered Sets 1

引用

9th International Symposium on parameterized and Exact Computation (IPEC)

作者： Bova, Simone Ganian, Robert Szeider, Stefan Vienna Univ Technol A-1040 Vienna Austria

ISBN: (数字)9783319135243

ISBN: (纸本)9783319135243;9783319135236

We study the computational problem of checking whether a quantified conjunctive query (a first-order sentence built using only conjunction as Boolean connective) is true in a finite poset (a reflexive, antisymmetric, and transitive directed graph). We prove that the problem is already NP-hard on a certain fixed poset, and investigate structural properties of posets yielding fixed-parameter tractability when the problem is parameterized by the query. Our main algorithmic result is that model checking quantified conjunctive queries on posets of bounded width is fixed-parameter tractable (the width of a poset is the maximum size of a subset of pairwise incomparable elements). We complement our algorithmic result by complexity results with respect to classes of finite posets in a hierarchy of natural poset invariants, establishing its tightness in this sense.

关键词： Quantified conjunctive queries Posets parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

complexity of Dense Bicluster Editing Problems

引用

20th International Conference on Computing and Combinatorics (COCOON)

作者： Sun, Peng Guo, Jiong Baumbach, Jan Max Planck Inst Informat Campus E1 4 D-66123 Saarbrucken Germany Univ So Denmark Inst Math & Comp Sci DK-5230 Odense Denmark MMCI Cluster Excellence D-66123\ Saarbrucken Germany

ISBN: (纸本)9783319087832;9783319087825

Given a density measure H, an undirected graph G and a nonnegative integer k, a H-CLUSTER EDITING problem is to decide whether G can be modified into a graph where all connected components are H-cliques, by at most k edge modifications. Previous studies have been conducted on the complexity and fixed-parameter tractability (FPT) of H-CLUSTER EDITING based on several different density measures. However, whether these conclusions hold on bipartite graphs is yet to be examined. In this paper, we focus on three different density measures for bipartite graphs: (1) having at most 8 missing edges for each vertex (s-biplex), (2) having average degree at least V 8 (average-s-biplex) and (3) having at most 8 missing edges within a single disjoint component (8-defective bicliques). First, the NP-completeness of the three problems is discussed and afterwards we show all these problems are fixed-parameter tractable with respect to the parameter (8,k).

关键词： Bicluster editing parameterized complexity Data reduction NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Explicit Linear Kernels via Dynamic Programming 31

Explicit Linear Kernels via Dynamic Programming

引用

31st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Garnero, Valentin Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. CNRS AlGCo Project Team Montpellier France Univ Montpellier 2 LIRMM Montpellier France Natl & Kapodistrian Univ Athens Dept Math Athens Greece

ISBN: (纸本)9783939897651

Several algorithmic meta-theorems on kernelization have appeared in the last years, starting with the result of Bodlaender et al. [FOCS 2009] on graphs of bounded genus, then generalized by Fomin et al. [SODA 2010] to graphs excluding a fixed minor, and by Kim et al. [ICALP 2013] to graphs excluding a fixed topological minor Typically, these results guarantee the existence of linear or polynomial kernels on sparse graph classes for problems satisfying some generic conditions but, mainly due to their generality, it is not clear how to derive from them constructive kernels with explicit constants. In this paper we make a step toward a fully constructive meta-kernelization theory on sparse graphs. Our approach is based on a more explicit protrusion replacement machinery that, instead of expressibility in CMSO logic, uses dynamic programming, which allows us to find an explicit upper bound on the size of the derived kernels. We demonstrate the usefulness of our techniques by providing the first explicit linear kernels for r-DOMINATING SET and r-SCATTERED SET on apex-minor-free graphs, and for PLANAR-F-DELETION on graphs excluding a fixed (topological) minor in the case where all the graphs in F are connected.

关键词： parameterized complexity linear kernels dynamic programming protrusion replacement graph minors

来源：评论

学校读者我要写书评

暂无评论

Controlling Elections with Bounded Single-Peaked Width 13

Controlling Elections with Bounded Single-Peaked Width

引用

International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Yang, Yongjie Guo, Jiong Univ Saarland Campus E 1-7 D-66123 Saarbrucken Germany

ISBN: (纸本)9781450327381

The problems of controlling an election have been shown NP-complete in general but polynomial-time solvable in single-peaked elections for many voting correspondences. To explore the complexity border, we consider these control problems by adding/deleting votes in elections with bounded single-peaked width k. Single-peaked elections have single-peaked width k = 1. We prove that the constructive control problems for Copeland(alpha) with 0 <= alpha < 1 turn out to be NP-hard even with k = 2, while for Copeland(1) and Maximin, the constructive control problems remain polynomial-time solvable with k = 2 but become NP-hard with k = 3. In contrast, we show that the constructive control problems for Condorcet and weak Condorcet and the destructive control problems for Maximin and Copeland(alpha) with 0 <= alpha <= 1 are all polynomial-time solvable with k being a constant;more precisely, these problems are fixed-parameter tractable (FPT) with k as parameter. A byproduct of our results is that the Young winner determination problem is FPT with respect to k. Finally, for the class of voting correspondences passing the Smith-IIA criterion we provide a general characterization to identify voting correspondences whose control problems are FPT with respect to k.

关键词： single-peaked width Condorcet Copeland Maximin Smith set parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of Some Geometric Problems in Unbounded Dimension

The Parameterized Complexity of Some Geometric Problems in U...

引用

4th International Workshop on parameterized and Exact Computation

作者： Giannopoulos, Panos Knauer, Christian Rote, Guenter Free Univ Berlin Inst Informat D-14195 Berlin Germany

ISBN: (纸本)9783642112683

We study the parameterized complexity of the following fundamental geometric problems with respect to the dimension d: i) Given n points in R-d, compute their minimum enclosing cylinder. ii) Given two n-point sets in Rd, decide whether they can be separated by two hyperplanes. iii) Given a system of n linear inequalities with d variables, find a maximum size feasible subsystem. We show that (the decision versions of) all these problems are W[1]-hard when parameterized by the dimension d. Our reductions also give n(Omega(d))-time lower bound (under the Exponential Time Hypothesis).

关键词： parameterized complexity geometric dimension lower bounds minimum enclosing cylinder maximum feasible subsystem 2-linear separability

来源：评论

学校读者我要写书评

暂无评论

The Tractability Frontier of Graph-Like First-Order Query Sets 14

The Tractability Frontier of Graph-Like First-Order Query Se...

引用

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Chen, Hubie Univ Basque Country Dept LSI E-20018 San Sebastian Spain Ikerbasque Basque Fdn Sci E-20018 San Sebastian Spain

ISBN: (纸本)9781450328869

We study first-order model checking, by which we refer to the problem of deciding whether or not a given first-order sentence is satisfied by a given finite structure. In particular, we aim to understand on which sets of sentences this problem is tractable, in the sense of parameterized complexity theory. To this end, we define the notion of a graph-like sentence set, which definition is inspired by previous work on first-order model checking wherein the permitted connectives and quantifiers were restricted. Our main theorem is the complete tractability classification of such graph-like sentence sets, which is (to our knowledge) the first complexity classification theorem concerning a class of sentences that has no restriction on the connectives and quantifiers. To present and prove our classification, we introduce and develop a novel complexity-theoretic framework which is built on parameterized complexity and includes new notions of reduction.

关键词： first-order queries query evaluation parameterized complexity treewidth

来源：评论

学校读者我要写书评

暂无评论

Model Checking Existential Logic on Partially Ordered Sets 14

Model Checking Existential Logic on Partially Ordered Sets

引用

Joint Meeting of the 23rd EACSL Annual Conference on Computer Science Logic (CSL) / 29th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Bova, Simone Ganian, Robert Szeider, Stefan Vienna Univ Technol Vienna Austria

ISBN: (纸本)9781450328869

We study the problem of checking whether an existential sentence (that is, a first-order sentence in prefix form built using existential quantifiers and all Boolean connectives) is true in a finite partially ordered set (in short, a poset). A poset is a reflexive, antisymmetric, and transitive digraph. The problem encompasses the fundamental embedding problem of finding an isomorphic copy of a poset as an induced substructure of another poset. Model checking existential logic is already NP-hard on a fixed poset;thus we investigate structural properties of posets yielding conditions for fixed-parameter tractability when the problem is parameterized by the sentence. We identify width as a central structural property (the width of a poset is the maximum size of a subset of pairwise incomparable elements);our main algorithmic result is that model checking existential logic on classes of finite posets of bounded width is fixed-parameter tractable. We observe a similar phenomenon in classical complexity, where we prove that the isomorphism problem is polynomial-time tractable on classes of posets of bounded width;this settles an open problem in order theory. We surround our main algorithmic result with complexity results on less restricted, natural neighboring classes of finite posets, establishing its tightness in this sense. We also relate our work with (and demonstrate its independence of) fundamental fixedparameter tractability results for model checking on digraphs of bounded degree and bounded clique-width.

关键词： Partially Ordered Sets Model Checking Width parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

全选清除本页清除全部题录导出标记到“检索档案”

共114页 << < 84 85 86 87 88 89 90 91 92 93 > >>

检索报告对象比较合并检索0

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

电话和邮箱必须正确填写，我们会与您联系确认。

联系人：

所在院系：

联系邮箱：

联系电话：

内蒙古自治区呼和浩特市赛罕区大学西街235号邮编: 010021

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：