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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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

分类表

所选分类

>> <<

限定检索结果

文献类型

816 篇 期刊文献
304 篇 会议
11 篇 学位论文

馆藏范围

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

日期分布

学科分类号

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

主题

1,131 篇 parameterized co...
124 篇 kernelization
97 篇 treewidth
57 篇 computational co...
55 篇 graph algorithms
43 篇 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 篇 w-hardness
19 篇 feedback vertex ...
18 篇 exact algorithms
18 篇 dominating set
18 篇 approximation

机构

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
18 篇 panolan fahad
18 篇 fomin fedor v
18 篇 yang yongjie
17 篇 paul christophe

语言

1,067 篇 英文
64 篇 其他

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

共 1131 条记录，以下是71-80 订阅

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

详细简洁

排序：

parameterized complexity of Discrete Morse Theory 13

Parameterized Complexity of Discrete Morse Theory

引用

29th Annual Symposium on Computational Geometry (SoCG)

作者： Burton, Benjamin A. Lewiner, Thomas Paixao, Joao Spreer, Jonathan Univ Queensland Sch Math & Phys Brisbane Qld Australia Pontificia Univ Catolica Rio de Janeiro Dept Math Rio de Janeiro Brazil

ISBN: (纸本)9781450320313

Optimal Morse matchings reveal essential structures of cell complexes which lead to powerful tools to study discrete geometrical objects, in particular discrete 3-manifolds. However, such matchings are known to be NP-hard to compute on 3-manifolds, through a reduction to the erasability problem. Here, we refine the study of the complexity of problems related to discrete Morse theory in terms of parameterized complexity. On the one hand we prove that the erasability problem is W[P]-complete on the natural parameter. On the other hand we propose an algorithm for computing optimal Morse matchings on triangulations of 3-manifolds which is fixed-parameter tractable in the treewidth of the bipartite graph representing the adjacency of the 1- and 2-simplexes. This algorithm also shows fixed parameter tractability for problems such as erasability and maximum alternating cycle-free matching. We further show that these results are also true when the treewidth of the dual graph of the triangulated 3-manifold is bounded. Finally, we investigate the respective treewidths of simplicial and generalized triangulations of 3-manifolds.

关键词： discrete Morse theory alternating cycle-free matching parameterized complexity fixed parameter tractability W[P]-completeness treewidth erasability collapsibility computational topology

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Multi-winner Determination: More Effort Towards Fixed-Parameter Tractability 17

Parameterized Complexity of Multi-winner Determination: More...

引用

17th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)

作者： Yang, Yongjie Wang, Jianxin Cent South Univ Sch Informat Sci & Engn Changsha Hunan Peoples R China Saarland Univ Chair Econ Theory Saarbrucken Germany

ISBN: (纸本)9781450356497

We study the k-committee selection rules minimax approval, proportional approval, and Chamberlin-Courant's approval. It is known that WINNER DETERMINATION for these rules is NP-hard. Moreover, the parameterized complexity of the problem has also been studied with respect to some natural parameters. However, there are still numerous parameterizations that have not been considered. We revisit the parameterized complexity of WINNER DETERMINATION for these rules by considering several important single parameters, combined parameters, and structural parameters, aiming at detecting as many fixed-parameter tractability results as possible.

关键词： multi-winner voting parameterized complexity approval voting tree-width maximum matching

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Weighted Target Set Selection 18th

Parameterized Complexity of Weighted Target Set Selection

引用

18th Annual Conference on Theory and Applications of Models of Computation (TAMC)

作者： Suzuki, Takahiro Kimura, Kei Suzuki, Akira Tamura, Yuma Zhou, Xiao Tohoku Univ Grad Sch Informat Sci Sendai Japan Kyushu Univ Fac Informat Sci & Elect Engn Fukuoka Japan

ISBN: (纸本)9789819723393;9789819723409

Consider a graph G where each vertex has a threshold. A vertex v in G is activated if the number of active vertices adjacent to v is at least as many as its threshold. A vertex subset A(0) of G is a target set if eventually all vertices in G are activated by initially activating vertices of A(0). The Target Set Selection problem (TSS) involves finding the smallest target set of G with vertex thresholds. This problem has already been extensively studied and is known to be NP-hard even for very restricted conditions. In this paper, we analyze TSS and its weighted variant, called the Weighted Target Set Selection problem (WTSS) from the perspective of parameterized complexity. Let k be the solution size and l be the maximum threshold. We first show that TSS is W[1]-hard for split graphs when parameterized by k + l, and W[2]-hard for cographs when parameterized by k. We also prove that WTSS is W[2]-hard for trivially perfect graphs when parameterized by k. On the other hand, we show that WTSS can be solved in O(n log n) time for complete graphs. Additionally, we design FPT algorithms for WTSS when parameterized by nd + l, tw + l, ce, and vc, where nd is the neighborhood diversity, tw is the treewidth, ce is the cluster editing number, and VC is the vertex cover number of the input graph.

关键词： parameterized complexity Graph algorithms Target set selection

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Gerrymandering 16th

Parameterized Complexity of Gerrymandering

引用

16th International Symposium on Algorithmic Game Theory (SAGT)

作者： Fraser, Andrew Lavallee, Brian Sullivan, Blair D. Univ Utah Salt Lake City UT 84112 USA

ISBN: (纸本)9783031432538;9783031432545

In a representative democracy, the electoral process involves partitioning geographical space into districts which each elect a single representative. These representatives craft and vote on legislation, incentivizing political parties to win as many districts as possible (ideally a plurality). Gerrymandering is the process by which district boundaries are manipulated to the advantage of a desired candidate or party. We study the parameterized complexity of Gerrymandering, a graph problem (as opposed to Euclidean space) formalized by Cohen-Zemach et al. (AAMAS 2018) and Ito et al. (AAMAS 2019) where districts partition vertices into connected subgraphs. We prove that Gerrymandering is W[2]-hard on trees (even when the depth is two) with respect to the number of districts k. Moreover, we show that Gerrymandering remains W[2]-hard in trees with l leaves with respect to the combined parameter k + l. In contrast, Gupta et al. (SAGT 2021) give an FPT algorithm for paths with respect to k. To complement our results and fill this gap, we provide an algorithm to solve Gerrymandering that is FPT in k when l is a fixed constant.

关键词： gerrymandering parameterized complexity graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of BANDWIDTH of Caterpillars and WEIGHTED PATH EMULATION 1

引用

47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Bodlaender, Hans L. Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands

ISBN: (数字)9783030868383

ISBN: (纸本)9783030868376;9783030868383

In this paper, we show that Bandwidth is hard for the complexity class W[t] for all t is an element of N, even for caterpillars with hair length at most three. As intermediate problem, we introduce the Weighted Path Emulation problem: given a vertex-weighted path P-N and integer M, decide if there exists a mapping of the vertices of P-N to a path P-M, such that adjacent vertices are mapped to adjacent or equal vertices, and such that the total weight of the pre-image of a vertex from P-M equals an integer c. We show that Weighted Path Emulation, with c as parameter, is hard for W[t] for all t is an element of N, and is strongly NP-complete. We also show that Directed Bandwidth is hard for W[t] for all t is an element of N, for directed acyclic graphs whose underlying undirected graph is a caterpillar.

关键词： Bandwidth parameterized complexity Weighted path emulation W-hierarchy Caterpillars

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity for Domination Problems on Degenerate Graphs

Parameterized Complexity for Domination Problems on Degenera...

引用

34th International Workshop on Graph-Theoretic Concepts in Computer Science

作者： Golovach, Petr A. Villanger, Yngve Univ Bergen Dept Informat N-5020 Bergen Norway

ISBN: (纸本)9783540922476

Domination problems are one of the classical types of problems in computer science. These problems are considered in many different versions and on different classes of graphs. We explore the boundary between fixed-parameter tractable and W-hard problems on sparse graphs. More precisely, we expand the list of domination probe lems which are fixed-parameter tractable(FPT) for degenerate graphs by proving that CONNECTED k-DOMINATING SET and k-DOMINATING THRESHOLD SET are FPT. From the other side we prove that there are domination problems which are difficult (W[1] or W[2]-hard) for this graph class. The PARTIAL k-DOMINATING SET and (k, r)-CENTER for r >= 2 are examples of such problems. It is also remarked that domination problems become difficult for graphs of hounded average degree.

关键词： parameterized complexity algorithms degenerate graphs domination

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Path Set Packing 17th

Parameterized Complexity of Path Set Packing

引用

17th International Conference and Workshops on Algorithms and Computation

作者： Aravind, N. R. Saxena, Roopam IIT Hyderabad Dept Comp Sci & Engn Hyderabad India

ISBN: (纸本)9783031270505;9783031270512

In PATH SET PACKING, the input is an undirected graph G, a collection P of simple paths in G, and a positive integer k. The problem is to decide whether there exist k edge-disjoint paths in P. We study the parameterized complexity of PATH SET PACKING with respect to both natural and structural parameters. We show that the problem is W[1]-hard with respect to vertex cover plus the maximum length of a path in P, and W[1]-hard with respect to pathwidth plus maximum degree plus solution size. These results answer an open question raised in [17]. On the positive side, we present an FPT algorithm parameterized by feedback vertex set plus maximum degree, and also provide an FPT algorithm parameterized by treewidth plus maximum degree plus maximum length of a path in P.

关键词： Path set packing Set packing parameterized complexity Fixed parameter tractability Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of the MINCCA Problem on Graphs of Bounded Decomposability 1

引用

42nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Gozupek, Didem Ozkan, Sibel Paul, Christophe Sau, Ignasi Shalom, Mordechai Gebze Tech Univ Dept Comp Engn Kocaeli Turkey Gebze Tech Univ Dept Math Kocaeli Turkey Univ Montpellier LIRMM CNRS Montpellier France TelHai Coll IL-12210 Upper Galilee Israel Bogazici Univ Dept Ind Engn Istanbul Turkey

ISBN: (数字)9783662535363

ISBN: (纸本)9783662535363;9783662535356

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence (MINCCA) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gozupek et al. [14] that the MINCCA problem is FPT when parameterized by the treewidth and the maximum degree of the input graph. In this article we present the following results for MINCCA: the problem is W[1]-hard parameterized by the treedepth of the input graph, even on graphs of average degree at most 8. In particular, it is W[1]-hard parameterized by the treewidth of the input graph, which answers the main open problem of [14];it is W[1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph;it is FPT parameterized by the star tree-cutwidth of the input graph, which is a slightly restricted version of tree-cutwidth. This result strictly generalizes the FPT result given in [14];it remains NP-hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs.

关键词： Minimum Changeover Cost Arborescence parameterized complexity FPT algorithm Treewidth Dynamic programming Planar graph

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Simultaneous Planarity 31st

Parameterized Complexity of Simultaneous Planarity

引用

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

作者： Fink, Simon D. Pfretzschner, Matthias Rutter, Ignaz Univ Passau Fak Informat & Math Passau Germany

ISBN: (纸本)9783031492747;9783031492754

Given k input graphs G((1)),..., G((k)), where each pair G((i)), G((j)) with i not equal j shares the same graph G, the problem SIMULTANEOUS EMBEDDING WITH FIXED EDGES (SEFE) asks whether there exists a planar drawing for each input graph such that all drawings coincide on G. While SEFE is still open for the case of two input graphs, the problem is NP-complete for k >= 3 [18]. In this work, we explore the parameterized complexity of SEFE. We show that SEFE is FPT with respect to k plus the vertex cover number or the feedback edge set number of the union graph G(boolean OR) = G((1)) boolean OR center dot center dot center dot boolean OR G((k)). Regarding the shared graph G, we show that SEFE is NP-complete, even if G is a tree with maximum degree 4. Together with a known NP-hardness reduction [1], this allows us to conclude that several parameters of G, including the maximum degree, the maximum number of degree-1 neighbors, the vertex cover number, and the number of cutvertices are intractable. We also settle the tractability of all pairs of these parameters. We give FPT algorithms for the vertex cover number plus either of the first two parameters and for the number of cutvertices plus the maximum degree, whereas we prove all remaining combinations to be intractable.

关键词： Simultaneous Planarity SEFE parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

parameterized complexity of Categorical Clustering with Size Constraints 17th

Parameterized Complexity of Categorical Clustering with Size...

引用

17th International Symposium on Algorithms and Data Structures (WADS)

作者： Fomin, Fedor, V Golovach, Petr A. Purohit, Nidhi Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783030835088;9783030835071

In the Categorical Clustering problem, we are given a set of vectors (matrix) A = {a(1), . . . , a(n)} over Sigma(m), where Sigma is a finite alphabet, and integers k and B. The task is to partition A into k clusters such that the median objective of the clustering in the Hamming norm is at most B. That is, we seek a partition {I-1, . . . , I-k} of {1, . . . , n} and vectors c(1), . . . , c(k) is an element of Sigma(m) such that Sigma(k)(i=1) Sigma(j is an element of Ii) d(H)(c(i), a(j)) <= B, where d(H)(a, b) is the Hamming distance between vectors a and b. Fomin, Golovach, and Panolan [ICALP 2018] proved that the problem is fixed-parameter tractable (for binary case Sigma = {0, 1}) by giving an algorithm that solves the problem in time 2(O(B logB)) . (mn)(O(1)). We extend this algorithmic result to a popular capacitated clustering model, where in addition the sizes of the clusters should satisfy certain constraints. More precisely, in CAPACITATED CLUSTERING, in addition, we are given two non-negative integers p and q, and seek a clustering with p <= vertical bar I-i vertical bar <= q for all i is an element of {1, . . . , k}. Our main theorem is that CAPACITATED CLUSTERING is solvable in time 2(O(B logB))vertical bar Sigma vertical bar(B) . (mn)(O(1)). The theorem not only extends the previous algorithmic results to a significantly more general model, it also implies algorithms for several other variants of CATEGORICAL CLUSTERING with constraints on cluster sizes.

关键词： Categorical clustering Capacitated clustering parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共114页 << < 4 5 6 7 8 9 10 11 12 13 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：