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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

164 篇 期刊文献
71 篇 会议
5 篇 学位论文

馆藏范围

240 篇 电子文献
0 种 纸本馆藏

日期分布

学科分类号

195 篇 工学
- 185 篇 计算机科学与技术...
- 46 篇 软件工程
- 5 篇 电气工程
- 3 篇 控制科学与工程
- 1 篇 石油与天然气工程
- 1 篇 生物工程
120 篇 理学
- 119 篇 数学
- 3 篇 统计学（可授理学、...
- 2 篇 生物学
15 篇 管理学
- 15 篇 管理科学与工程(可...
- 4 篇 工商管理
4 篇 经济学
- 4 篇 应用经济学
2 篇 法学
- 2 篇 法学
1 篇 医学
- 1 篇 临床医学

主题

240 篇 parameterized al...
29 篇 graph algorithms
24 篇 kernelization
22 篇 treewidth
20 篇 approximation al...
14 篇 exact algorithms
14 篇 parameterized co...
10 篇 dynamic programm...
7 篇 planar graphs
6 篇 tree decompositi...
6 篇 vertex cover
6 篇 steiner tree
5 篇 graphs
5 篇 tournaments
5 篇 exponential time...
5 篇 branchwidth
5 篇 chordal graphs
5 篇 minimum fill-in
5 篇 graph minors
5 篇 feedback vertex ...

机构

16 篇 univ elect sci &...
16 篇 univ bergen dept...
13 篇 univ bergen berg...
9 篇 univ bergen dept...
9 篇 univ trier fb ab...
8 篇 univ montpellier...
8 篇 inst math sci ma...
6 篇 inst math sci ch...
6 篇 ben gurion univ ...
5 篇 univ warsaw inst...
5 篇 hbni inst math s...
4 篇 texas a&m univ d...
4 篇 ben gurion univ ...
4 篇 tu wien algorith...
4 篇 univ bergen dept...
4 篇 texas a&m univ d...
3 篇 indian inst tech...
3 篇 univ bergen n-50...
3 篇 depaul univ sch ...
3 篇 univ saarland d-...

作者

25 篇 saurabh saket
21 篇 thilikos dimitri...
19 篇 xiao mingyu
16 篇 fernau henning
15 篇 fomin fedor v.
15 篇 lokshtanov danie...
8 篇 raman venkatesh
8 篇 zehavi meirav
7 篇 knop dusan
7 篇 sau ignasi
6 篇 pilipczuk marcin
6 篇 hecher markus
6 篇 panolan fahad
6 篇 golovach petr a.
6 篇 ramanujan m. s.
6 篇 gaspers serge
6 篇 fichte johannes ...
6 篇 stamoulis gianno...
5 篇 ordyniak sebasti...
5 篇 pilipczuk michal

语言

225 篇 英文
15 篇 其他

检索条件"主题词=Parameterized algorithms"

共 240 条记录，以下是181-190 订阅

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

详细简洁

排序：

Default Logic and Bounded Treewidth 1

引用

12th International Conference on Language and Automata Theory and Applications (LATA)

作者： Fichte, Johannes K. Hecher, Markus Schindler, Irina Tech Univ Wien Vienna Austria Leibniz Univ Hannover Hannover Germany

ISBN: (数字)9783319773131

ISBN: (纸本)9783319773131;9783319773124

In this paper, we study Reiter's propositional default logic when the treewidth of a certain graph representation (semi-primal graph) of the input theory is bounded. We establish a dynamic programming algorithm on tree decompositions that decides whether a theory has a consistent stable extension (ExT). Our algorithm can even be used to enumerate all generating defaults (ENuMSE) that lead to stable extensions. We show that our algorithm decides EXT in linear time in the input theory and triple exponential time in the treewidth (so-called fixed-parameter linear algorithm). Further, our algorithm solves ENuMSE with a pre-computation step that is linear in the input theory and triple exponential in the treewidth followed by a linear delay to output solutions.

关键词： parameterized algorithms Tree decompositions Dynamic programming Reiter's default logic Propositional logic

来源：评论

学校读者我要写书评

暂无评论

Between Treewidth and Clique-Width 40

引用

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

作者： Saether, Sigve Hortemo Telle, Jan Arne Univ Bergen Dept Informat N-5008 Bergen Norway

ISBN: (纸本)9783319123394

Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al. (Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 493-502, 2010a;SIAM J Comput 39(5):1941-1956, 2010b). We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle (New width parameters of graphs. The University of Bergen, 2012) on maximum matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.

关键词： parameterized algorithms Width parameters of graphs Split decompositions

来源：评论

学校读者我要写书评

暂无评论

Finding Even Cycles Faster via Capped k-Walks 2017

Finding Even Cycles Faster via Capped <i>k</i>-Walks

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Dahlgaard, Soren Knudsen, Mathias Baek Tejs Stoeckel, Morten Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450345286

Finding cycles in graphs is a fundamental problem in algorithmic graph theory. In this paper, we consider the problem of finding and reporting a cycle of length 2k in an undirected graph G with n nodes and m edges for constant k >= 2. A classic result by Bondy and Simonovits [J. Combinatorial Theory, 1974] implies that if m >= 100kn(1+1/k), then G contains a 2k-cycle, further implying that one needs to consider only graphs with m = O(n(1+1/k)). Previously the best known algorithms were an O(n(2)) algorithm due to Yuster and Zwick [J. Discrete Math 1997] as well as a O(m(2)-((1+[k/2]-1)/(k+1))) algorithm by Alon et. al. [Algorithmica 1997]. We present an algorithm that uses O(m(2k/(k+1))) time and finds a 2k-cycle if one exists. This bound is O(n(2)) exactly when m = Theta(n(1+1/k)). When finding 4-cycles our new bound coincides with Alon et. al., while for every k > 2 our new bound yields a polynomial improvement in m. Yuster and Zwick noted that it is "plausible to conjecture that O(n(2)) is the best possible bound in terms of n". We show "conditional optimality": if this hypothesis holds then our O(m(2k/(k+1))) algorithm is tight as well. Furthermore, a folklore reduction implies that no combinatorial algorithm can determine if a graph contains a 6-cycle in time O(m(3/2-epsilon)) for any epsilon > 0 unless boolean matrix multiplication can be solved combinatorially in time O(n(3-epsilon')) for some epsilon' > 0, which is widely believed to be false. Coupled with our main result, this gives tight bounds for finding 6-cycles combinatorially and also separates the complexity of finding 4- and 6-cycles giving evidence that the exponent of m in the running time should indeed increase with k. The key ingredient in our algorithm is a new notion of capped k-walks, which are walks of length k that visit only nodes according to a fixed ordering. Our main technical contribution is an involved analysis proving several properties of such walks which may be of independent inter

关键词： Graph algorithms Cycles parameterized algorithms graph walks capped walks conditional lower bounds

来源：评论

学校读者我要写书评

暂无评论

Exploiting Treewidth for Projected Model Counting and Its Limits 21st

Exploiting Treewidth for Projected Model Counting and Its Li...

引用

21st International Conference on Theory and Applications of Satisfiability Testing (SAT) Held as Part of the Federated Logic Conference (FloC)

作者： Fichte, Johannes K. Hecher, Markus Morak, Michael Woltran, Stefan TU Wien Inst Log & Computat Vienna Austria

ISBN: (纸本)9783319941448;9783319941431

In this paper, we introduce a novel algorithm to solve projected model counting (PMC). PMC asks to count solutions of a Boolean formula with respect to a given set of projected variables, where multiple solutions that are identical when restricted to the projected variables count as only one solution. Our algorithm exploits small treewidth of the primal graph of the input instance. It runs in time O(2(2k+4) n(2)) where k is the treewidth and n is the input size of the instance. In other words, we obtain that the problem PMC is fixed-parameter tractable when parameterized by treewidth. Further, we take the exponential time hypothesis (ETH) into consideration and establish lower bounds of bounded treewidth algorithms for PMC, yielding asymptotically tight runtime bounds of our algorithm.

关键词： parameterized algorithms Tree decompositions Multi-pass dynamic programming Projected model counting Propositional logic

来源：评论

学校读者我要写书评

暂无评论

FPT algorithms to Enumerate and Count Acyclic and Totally Cyclic Orientations 10th

FPT Algorithms to Enumerate and Count Acyclic and Totally Cy...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Oliveira, Farley Soares Hiraishi, Hidefumi Imai, Hiroshi Univ Tokyo Dept Comp Sci Tokyo Japan

In this paper, we deal with counting and enumerating problems for two types of graph orientations: acyclic and totally cyclic orientations. Counting is known to be #P-hard for both of them. To circumvent this issue, we propose Fixed Parameter Tractable (FPT) algorithms. For the enumeration task, we construct a Binary Decision Diagram (BDD) to represent all orientations of the two kinds, instead of explicitly enumerating them. We prove that the running time of this construction is bounded by O*(2(pw2/4+o(PW2))) with respect to the pathwidth pw. We then develop faster FPT algorithms to count acyclic and totally acyclic orientations, running in O*(2(bw2/2+o(bw2))) time, where bw denotes the branch-width of the given graph. These counting algorithms are obtained by applying the observations in our enumerating algorithm to branch decomposition.

关键词： Acyclic Orientations Totally Cyclic Orientations parameterized algorithms FPT algorithms Path-width Branch-width Binary Decision Diagram

来源：评论

学校读者我要写书评

暂无评论

Locating the Eigenvalues for Graphs of Small Clique-Width 13th

Locating the Eigenvalues for Graphs of Small Clique-Width

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Furer, Martin Hoppen, Carlos Jacobs, David P. Trevisan, Vilmar Penn State Univ Dept Comp Sci & Engn State Coll PA 16801 USA Univ Fed Rio Grande do Sul Inst Matemat Alegre Brazil Clemson Univ Sch Comp Clemson SC USA

It is shown that if G has clique-width k, and a corresponding tree decomposition is known, then a diagonal matrix congruent to A-cI for constants c, where A is the adjacency matrix of the graph G of order n, can be co... 详细信息

ISBN: (纸本)9783319774046;9783319774039

关键词： Eigenvalues Clique-width Congruent matrices Efficient algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Turan's Theorem Through Algorithmic Lens 49th

Turan's Theorem Through Algorithmic Lens

引用

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

作者： Fomin, Fedor V. Golovach, Petr A. Sagunov, Danil Simonov, Kirill Univ Bergen Dept Informat Bergen Norway Steklov Inst Math St Petersburg Dept St Petersburg Russia Univ Potsdam Hasso Plattner Inst Potsdam Germany

ISBN: (纸本)9783031433795;9783031433801

The fundamental theorem of Tur ' an from Extremal Graph Theory determines the exact bound on the number of edges t(r)(n) in an n-vertex graph that does not contain a clique of size r + 1. We establish an interesting link between Extremal Graph Theory and algorithms by providing a simple compression algorithm that in linear time reduces the problem of finding a clique of size l in an n-vertex graph G with m >= t(r)(n) - k edges, where l <= r + 1, to the problem of finding a maximum clique in a graph on at most 5k vertices. This also gives us an algorithm deciding in time 2.49(k) center dot (n + m) whether G has a clique of size l. As a byproduct of the new compression algorithm, we give an algorithm that in time 2(O(td2)) center dot n(2) decides whether a graph contains an independent set of size at least n/(d+ 1)+ t. Here d is the average vertex degree of the graph G. The multivariate complexity analysis based on ETH indicates that the asymptotical dependence on several parameters in the running times of our algorithms is tight.

关键词： parameterized algorithms Extremal graph theory Turan's theorem Above guarantee Kernelization Exponential time hypothesis

来源：评论

学校读者我要写书评

暂无评论

Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes 24

Model Checking Disjoint-Paths Logic on Topological-Minor-Fre...

引用

39th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)

作者： Schirrmacher, Nicole Siebertz, Sebastian Stamoulis, Giannos Thilikos, Dimitrios M. Vigny, Alexandre Bremen Univ Bremen Germany Univ Warsaw Warsaw Poland Univ Montpellier LIRMM CNRS Montpellier France Univ Clermont Auvergne Clermont Ferrand France

ISBN: (纸本)9798400706608

Disjoint-paths logic, denoted FO+ DP, extends first-order logic (FO) with atomic predicates dp(k) [(x(1),y(1)),..., (s(k),y(k))], expressing the existence of internally vertex-disjoint paths between x(i) and y(i), for 1 <= i <= k. We prove that for every graph class excluding some fixed graph as a topological minor, the model checking problem for FO+DP is fixed-parameter tractable. This extends the model checking algorithm of Golovach et al. [SODA 2023] for FO+DP for minor-closed graph classes. It also essentially settles the question of tractable model checking for this logic on subgraph-closed classes, since the problem is hard on subgraph-closed classes not excluding a topological minor (assuming a further mild condition on efficiency of encoding).

关键词： Model checking Topological-minor-free graphs First-order logic Disjoint paths parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Fast Sub-exponential algorithms and Compactness in Planar Graphs

Fast Sub-exponential Algorithms and Compactness in Planar Gr...

引用

19th Annual European Symposium on algorithms (ESA)

作者： Thilikos, Dimitrios M. Univ Athens Dept Math Athens 15784 Greece

ISBN: (纸本)9783642237195

We provide a new theory, alternative to bidimensionality, of sub-exponential parameterized algorithms on planar graphs, which is based on the notion of compactness. Roughly speaking, a parameterized problem is (r, q)-compact when all the faces and vertices of its YES-instances are "r-radially dominated" by some vertex set whose size is at most q times the parameter. We prove that if a parameterized problem can be solved in c(branchwidth(G)) n(O(1)) steps and is (r, q)-compact, then it can be solved by a c(*** q.k) n(O(1)) step algorithm (where k is the parameter). Our framework is general enough to unify the analysis of almost all known sub-exponential parameterized algorithms on planar graphs and improves or matches their running times. Our results are based on an improved combinatorial bound on the branchwidth of planar graphs that bypasses the grid-minor exclusion theorem. That way, our approach encompasses new problems where bidimensionality theory do not directly provide sub-exponential parameterized algorithms.

关键词： parameterized algorithms Branchwidth Planar Graphs

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms via Monotone Local Search 16

Exact Algorithms via Monotone Local Search

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Fomin, Fedor V. Gaspers, Serge Lokshtanov, Daniel Saurabh, Saket Univ Bergen Bergen Norway UNSW Australia Sydney NSW Australia CSIRO Data61 Canberra ACT Australia Inst Math Sci Madras Tamil Nadu India

ISBN: (纸本)9781450341325

We give a new general approach for designing exact exponential -time algorithms for subset problems. In a subset problem the input implicitly describes a family of sets over a universe of size n and the task is to determine whether the family contains at least one set. A typical example of a subset problem is WEIGHTED d-SAT. Here, the input is a CNF-formula with clauses of size at most d, and an integer W. The universe is the set of variables and the variables have integer weights. The family contains all the subsets S of variables such that the total weight of the variables in S does not exceed W, and setting the variables in S to 1 and the remaining variables to 0 satisfies the formula. Our approach is based on "monotone local search", where the goal is to extend a partial solution to a solution by adding as few elements as possible. More formally, in the extension problem we are also given as input a subset X of the universe and an integer k. The task is to determine whether one can add at most k elements to X to obtain a set in the (implicitly defined) family. Our main result is that a c(k)n(O(1)) time algorithm for the extension problem immediately yields a randomized algorithm for finding a solution of any size with running time O((2-1/c)n). In many cases, the extension problem can be reduced to simply finding a solution of size at most k. Furthermore, efficient algorithms for finding small solutions have been extensively studied in the field of parameterized algorithms. Directly applying these algorithms, our theorem yields in one stroke significant improvements over the best known exponential-time algorithms for several well-studied problems, including d-HITTING SET, FEEDBACK VERTEX SET, NODE UNIQUE LABEL COVER, and WEIGHTED d-SAT. Our results demonstrate an interesting and very concrete connection between parameterized algorithms and exact exponential time algorithms. We also show how to derandomize our algorithms at the cost of a subexponential multiplicat

关键词： Combinatorial bounds exponential time algorithms parameterized algorithms randomized algorithms subset problems

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：