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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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 篇 期刊文献
306 篇 会议
11 篇 学位论文

馆藏范围

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

日期分布

学科分类号

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

主题

1,138 篇 parameterized co...
127 篇 kernelization
97 篇 treewidth
58 篇 computational co...
56 篇 graph algorithms
44 篇 vertex cover
42 篇 algorithms
41 篇 fixed-parameter ...
34 篇 dynamic programm...
27 篇 approximation al...
24 篇 planar graphs
21 篇 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 篇 tu berlin inst s...
16 篇 ben gurion univ ...
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...
22 篇 tsur dekel
22 篇 hermelin danny
20 篇 marx daniel
19 篇 panolan fahad
18 篇 fomin fedor v
18 篇 yang yongjie
17 篇 paul christophe

语言

1,071 篇 英文
65 篇 其他

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

共 1138 条记录，以下是171-180 订阅

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

详细简洁

排序：

Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) 31

Everything you always wanted to know about the parameterized...

引用

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

作者： Marx, Daniel Pilipczuk, Michal Hungarian Acad Sci MTA SZTAKI Comp & Automat Res Inst Budapest Hungary Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783939897651

Given two graphs H and G, the SUBGRAPH ISOMORPHISM problem asks if H is isomorphic to a subgraph of G. While NP-hard in general, algorithms exist for various parameterized versions of the problem. However, the literature contains very little guidance on which combinations of parameters can or cannot be exploited algorithmically. Our goal is to systematically investigate the possible parameterized algorithms that can exist for SUBGRAPH ISOMORPHISM. We develop a framework involving 10 relevant parameters for each of H and G (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time ft (p(1),p(2), ..., p(l)) . n(f2(pl+1, ..., pk)) exists, where each of p(1), ..., p(k) is one of the 10 parameters depending only on H or G. We show that all the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs);some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of G gives rise to a highly nontrivial algorithm for SUBGRAPH ISOMORPHISM. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when H is a bounded-degree tree of constant pathwidth and G is a planar graph of bounded pathwidth.

关键词： parameterized complexity subgraph isomorphism

来源：评论

学校读者我要写书评

暂无评论

Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and parameterized complexity 27

Degree-Constrained Orientation of Maximum Satisfaction: Grap...

引用

27th Annual International Symposium on Algorithms and Computation (ISAAC)

作者： Bodlaender, Hans L. Ono, Hirotaka Otachi, Yota Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Univ Technol Eindhoven Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands Nagoya Univ Grad Sch Informat Chikusa Ku Furo Cho Nagoya Aichi 4648601 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan

ISBN: (纸本)9783959770262

The problem MAX W-LIGHT (MAX W-HEAVY) for an undirected graph is to assign a direction to each edge so that the number of vertices of outdegree at most W (resp. at least W) is maximized. It is known that these problems are NP-hard even for fixed W. For example, MAX 0- LIGHT is equivalent to the problem of finding a maximum independent set. In this paper, we show that for any fixed constant W, MAX W-HEAVY can be solved in linear time for hereditary graph classes for which treewidth is bounded by a function of degeneracy. We show that such graph classes include chordal graphs, circular-arc graphs, d-trapezoid graphs, chordal bipartite graphs, and graphs of bounded clique-width. To have a polynomial-time algorithm for MAX W-LIGHT, we need an additional condition of a polynomial upper bound on the number of potential maximal cliques to apply the metatheorem by Fomin et al. (SIAM J Comput 44:54-87, 2015). The aforementioned graph classes, except bounded clique-width graphs, satisfy such a condition. For graphs of bounded clique-width, we present a dynamic programming approach not using the metatheorem to show that it is actually polynomial-time solvable for this graph class too. We also study the parameterized complexity of the problems and show some tractability and intractability results.

关键词： Orientation Graph class Width parameter parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Learning First-Order Logic 22

On the Parameterized Complexity of Learning First-Order Logi...

引用

41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： van Bergerem, Steffen Grohe, Martin Ritzert, Martin Rhein Westfal TH Aachen Aachen Germany Aarhus Univ Aarhus Denmark

ISBN: (纸本)9781450392600

We analyse the complexity of learning first-order queries in a model-theoretic framework for supervised learning introduced by (Grohe and Turan, TOCS 2004). Previous research on the complexity of learning in this framework focussed on the question of when learning is possible in time sublinear in the background structure. Here we study the parameterized complexity of the learning problem. We have two main results. The first is a hardness result, showing that learning first-order queries is at least as hard as the corresponding model-checking problem, which implies that on general structures it is hard for the parameterized complexity class AW[*]. Our second main contribution is a fixed-parameter tractable agnostic PAC learning algorithm for first-order queries over sparse relational data (more precisely, over nowhere dense background structures).

关键词： first-order query learning agnostic probably approximately correct learning nowhere dense graph parameterized complexity fixed-parameter tractable Boolean classification supervised learning first-order logic

来源：评论

学校读者我要写书评

暂无评论

Matrix Rigidity from the Viewpoint of parameterized complexity 34

Matrix Rigidity from the Viewpoint of Parameterized Complexi...

引用

34th Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fomin, Fedor V. Lokshtanov, Daniel Meesum, S. M. Saurabh, Saket Zehavi, Meirav Univ Bergen Bergen Norway Inst Math Sci Chennai Tamil Nadu India

ISBN: (纸本)9783959770286

The rigidity of a matrix A for a target rank r over a field IF is the minimum Hamming distance between A and a matrix of rank at most r. Rigidity is a classical concept in Computational complexity Theory: constructions of rigid matrices are known to imply lower bounds of significant importance relating to arithmetic circuits. Yet, from the viewpoint of parameterized complexity, the study of central properties of matrices in general, and of the rigidity of a matrix in particular, has been neglected. In this paper, we conduct a comprehensive study of different aspects of the computation of the rigidity of general matrices in the framework of parameterized complexity. Naturally, given parameters r and k, the MATRIX RIGIDITY problem asks whether the rigidity of A for the target rank r is at most k. We show that in case F = R or F is any finite field, this problem is fixed-parameter tractable with respect to k + r. To this end, we present a dimension reduction procedure, which may be a valuable primitive in future studies of problems of this nature. We also employ central tools in Real Algebraic Geometry, which are not well known in parameterized complexity, as a black box. In particular, we view the output of our dimension reduction procedure as an algebraic variety. Our main results are complemented by a W[1]-hardness result and a subexponential-time parameterized algorithm for a special case of MATRIX RIGIDITY, highlighting the different flavors of this problem.

关键词： Matrix Rigidity parameterized complexity Linear Algebra

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of Bend-Minimum Orthogonal Planarity 31st

On the Parameterized Complexity of Bend-Minimum Orthogonal P...

引用

31st International Symposium on Graph Drawing and Network Visualization (GD)

作者： Di Giacomo, Emilio Didimo, Walter Liotta, Giuseppe Montecchiani, Fabrizio Ortali, Giacomo Univ Perugia Dipartimento Ingn Perugia Italy

ISBN: (纸本)9783031492747;9783031492754

Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number of bends, the number of vertices of degree at most two, and the treewidth of the input graph (Di Giacomo et al., 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in FPT parameterized by the number of vertices of degree at most two.

关键词： Orthogonal drawings bend-minimization 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

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of d-Restricted Boolean Net Synthesis 16th

On the Parameterized Complexity of d-Restricted Boolean Net ...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Tredup, Ronny Erofeev, Evgeny Univ Rostock Inst Informat Theoret Informat Albert Einstein Str 22 D-18059 Rostock Germany Carl von Ossietzky Univ Oldenburg Dept Comp Sci D-26111 Oldenburg Germany

In this paper, we investigate the parameterized complexity of d-restricted tau-synthesis (dR tau S) parameterized by d for a range of Boolean types of nets tau. We show that dR tau S is W[1]-hard for 64 of 128 possibl... 详细信息

ISBN: (纸本)9783030592660;9783030592677

关键词： Synthesis parameterized complexity Boolean Petri net

来源：评论

学校读者我要写书评

暂无评论

On parameterized complexity of Group Activity Selection Problems on Social Networks 16

On Parameterized Complexity of Group Activity Selection Prob...

引用

16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)

作者： Igarashi, Ayumi Bredereck, Robert Elkind, Edith Univ Oxford Oxford England

ISBN: (纸本)9781510855076

In Group Activity Selection Problem with graph structure (gGASP), players form coalitions to participate in activities and have preferences over pairs of the form (activity, group size);moreover, a group of players can only engage in the same activity if the members of the group form a connected subset of the underlying communication structure. We study the parameterized complexity of finding outcomes of gGASP that are Nash stable, individually stable or core stable. For the parameter 'number of activities', we propose an FPT algorithm for Nash stability for the case where the social network is acyclic and obtain a W[1]-hardness result for cliques (i.e., for classic GASP);similar results hold for individual stability. In contrast, finding a core stable outcome is hard even if the number of activities is bounded by a small constant, both for classic GASP and when the social network is a star. For the parameter 'number of players', all problems we consider are in XP for arbitrary social networks;on the other hand, we prove W[1]-hardness results with respect to the parameter 'number of players' for the case where the social network is a clique (i.e., for classic GASP).

关键词： Group activity selection problems social networks parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

The parameterized complexity of the Equidomination Problem 43rd

The Parameterized Complexity of the Equidomination Problem

引用

43rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Schaudt, Oliver Senger, Fabian Univ Cologne Inst Informat Weyertal 80 D-50931 Cologne Germany

ISBN: (纸本)9783319687056;9783319687049

A graph G = (V, E) is called equidominating if there exists a value t is an element of IN and a weight function omega: V -> IN such that the total weight of a subset D subset of V is equal to t if and only if D is a minimal dominating set. To decide whether or not a given graph is equidominating is referred to as the EQUIDOMINATION problem. In this paper we show that two parameterized versions of the EQUIDOMINATION problem are fixed-parameter tractable: the first parameterization considers the target value t leading to the TARGET- t EQUIDOMINATION problem. The second parameterization allows only weights up to a value k, which yields the k- EQUIDOMINATION problem. In addition, we characterize the graphs whose every induced subgraph is equidominating. We give a finite forbidden induced subgraph characterization and derive a fast recognition algorithm.

关键词： Minimal dominating set Equidominating graph Kernelization parameterized complexity Hereditary property

来源：评论

学校读者我要写书评

暂无评论

Partition Sort versus Quick Sort: A Comparative Average Case Analysis with Special Emphasis on parameterized complexity

引用

2nd International Conference on Advances in Computing and Information Technology (ACITY 2012)

作者： Singh, Niraj Kumar Chakraborty, Soubhik BIT Mesra Dept Appl Math Ranchi 835215 Bihar India BIT Mesra Dept Comp Sci & Engn Ranchi 835215 Bihar India

ISBN: (纸本)9783642315510

In our previous work we introduced Partition sort and found it to be more robust compared to the Quick sort in average case. This paper does a more comprehensive comparative study of the relative performance of these two algorithms with focus on parameterized complexity analysis. The empirical results revealed that Partition sort is the better choice for discrete distribution inputs, whereas Quick sort was found to have a clear edge for continuous data sets.

关键词： Partition Sort Quick sort average case parameterized complexity robustness

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共114页 << < 14 15 16 17 18 19 20 21 22 23 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：