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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

当前已输入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 条记录，以下是201-210 订阅

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

详细简洁

排序：

Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract) 1

引用

24th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Chauve, Cedric Jones, Mark Lafond, Manuel Scornavacca, Celine Weller, Mathias Simon Fraser Univ Dept Math Burnaby BC Canada Delft Univ Technol Delft Inst Appl Math POB 5 NL-2600 AA Delft Netherlands Univ Ottawa Dept Math & Stat Ottawa ON Canada Univ Montpellier CNRS EPHE Inst Sci EvolutIRD Montpellier France Univ Montpellier Lab Informat Robot & Microelect Montpellier IBC Montpellier France

ISBN: (数字)9783319674285

ISBN: (纸本)9783319674285;9783319674278

Understanding the evolution of a set of genes or species is a fundamental problem in evolutionary biology. The problem we study here takes as input a set of trees describing possibly discordant evolutionary scenarios for a given set of genes or species, and aims at finding a single tree that minimizes the leaf-removal distance to the input trees. This problem is a specific instance of the general consensus/super-tree problem, widely used to combine or summarize discordant evolutionary trees. The problem we introduce is specifically tailored to address the case of discrepancies between the input trees due to the misplacement of individual taxa. Most supertree or consensus tree problems are computationally intractable, and we show that the problem we introduce is also NP-hard. We provide tractability results in form of a 2-approximation algorithm and a parameterized algorithm with respect to the number of removed leaves. We also introduce a variant that minimizes the maximum number d of leaves that are removed from any input tree, and provide a parameterized algorithm for this problem with parameter d.

关键词： Computational biology Phylogenetics parameterized algorithms Approximation Consensus trees Leaf deletion

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth 55

Fixed-parameter tractable canonization and isomorphism test ...

引用

55th Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Lokshtanov, Daniel Pilipczuk, Marcin Pilipczuk, Michal Saurabh, Saket Univ Bergen N-5020 Bergen Norway Inst Math Sci Thiruvananthapuram Kerala India

ISBN: (纸本)9781479965175

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G(1), G(2), either concludes that one of these graphs has treewidth at least k, or determines whether G(1) and G(2) are isomorphic. The running time of the algorithm on an n-vertex graph is 2(O(k5 log k)) . n(5), and this is the first fixed-parameter algorithm for GRAPH ISOMORPHISM parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2(O(k5 log k)) . n(5) time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k(4)). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G(1) and G(2) are equal.

关键词： graph isomorphism canonization parameterized algorithms treewidth

来源：评论

学校读者我要写书评

暂无评论

Dynamic treewidth 64

Dynamic treewidth

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Korhonen, Tuukka Majewski, Konrad Nadara, Wojciech Pilipczuk, Michal Sokolowski, Marek Univ Bergen Dept Informat Bergen Norway Univ Warsaw Inst Informat Warsaw Poland

ISBN: (纸本)9798350318944

We present a data structure that for a dynamic graph G that is updated by edge insertions and deletions, maintains a tree decomposition of G of width at most 6k + 5 under the promise that the treewidth of G never grows above k. The amortized update time is O-k(2(root log n log log n)), where n is the vertex count of G and the O-k(.) notation hides factors depending on k. In addition, we also obtain the dynamic variant of Courcelle's Theorem: for any fixed property phi expressible in the CMSO2 logic, the data structure can maintain whether G satisfies phi within the same time complexity bounds. To a large extent, this answers a question posed by Bodlaender [WG 1993].

关键词： treewidth parameterized algorithms dynamic algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

An FPT-algorithm for recognizing k-apices of minor-closed graph classes 47

An FPT-algorithm for recognizing k-apices of minor-closed gr...

引用

47th International Colloquium on Automata, Languages, and Programming, ICALP 2020

作者： Sau, Ignasi Stamoulis, Giannos Thilikos, Dimitrios M. LIRMM Université de Montpellier CNRS France Department of Informatics and Telecommunications National and Kapodistrian University of Athens Greece Athens Greece

ISBN: (纸本)9783959771382

Let G be a graph class. We say that a graph G is a k-apex of G if G contains a set S of at most k vertices such that G\S belongs to G. We prove that if G is minor-closed, then there is an algorithm that either returns a set S certifying that G is a k-apex of G or reports that such a set does not exist, in 2poly(k)n3 time. Here poly is a polynomial function whose degree depends on the maximum size of a minor-obstruction of G, i.e., the minor-minimal set of graphs not belonging to G. In the special case where G excludes some apex graph as a minor, we give an alternative algorithm running in 2poly(k)n2 time. © Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos;licensed under Creative Commons License CC-BY 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020).

关键词： Graph minors Graph modification problems Irrelevant vertex technique parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Packing paths: Recycling saves time 8

Packing paths: Recycling saves time

引用

8th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2009

作者： Fernau, Henning Raible, Daniel Universität Trier FB 4 - Abteilung Informatik TrierD-54286 Germany

来源：评论

学校读者我要写书评

暂无评论

Reducing Reachability in Temporal Graphs: Towards a More Realistic Model of Real-World Spreading Processes 1

引用

18th Conference on Computability in Europe (CiE)

作者： Meeks, Kitty Univ Glasgow Sch Comp Sci Glasgow G12 8RZ Lanark Scotland

ISBN: (数字)9783031087400

ISBN: (纸本)9783031087400;9783031087394

In many settings there is a need to reduce the spread of something undesirable, such as a virus, through a network. Typically, the network in which the spreading process takes place is not fixed but is subject to discrete changes over time;a natural formalism for such networks is that of temporal graphs. In this paper we survey three types of modifications that have been proposed in order to reduce reachability in temporal graphs, as well as the computational complexity of identifying optimal strategies for reducing reachability using each type of modification. We then go on to discuss several limitations of the current frameworks as models for intervention against real-world spreading processes, and suggest how these might be addressed in future research.

关键词： Reachability Temporal graphs Spreading processes Computational complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

On Two Techniques of Combining Branching and Treewidth

On Two Techniques of Combining Branching and Treewidth

引用

17th International Symposium on algorithms and Computation (ISAAC 2006)

作者： Fomin, Fedor V. Gaspers, Serge Saurabh, Saket Stepanov, Alexey A. Univ Bergen Dept Informat N-5020 Bergen Norway Inst Math Sci Chennai 600113 Tamil Nadu India

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of NP hard problems. All our algorithms require non-trivial balancing of these two techniques. In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the fastest known algorithms for MINIMUM MAXIMAL MATCHING and for counting all 3-colorings of a graph. In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a graph. We also discuss how similar techniques can be used to design faster parameterized algorithms.

关键词： Exact exponential time algorithms parameterized algorithms NP hard problems Treewidth #3-Coloring #Minimum dominating set Minimum maximal matching k-Weighted vertex cover

来源：评论

学校读者我要写书评

暂无评论

Graph Editing to a Given Neighbourhood Degree List is Fixed-Parameter Tractable

Graph Editing to a Given Neighbourhood Degree List is Fixed-...

引用

作者： Subramanya, Vijay University of Waterloo

学位级别：硕士

Graph editing problems have a long history and have been widely studied, with applications in biochemistry and complex network analysis. They generally ask whether an input graph can be modified by inserting and deleting vertices and edges to a graph with the desired property. We consider the problem \textsc{Graph-Edit-to-NDL} (GEN) where the goal is to modify to a graph with a given neighbourhood degree list (NDL). The NDL lists the degrees of the neighbours of vertices in a graph, and is a stronger invariant than the degree sequence, which lists the degrees of vertices. We show \textsc{Graph-Edit-to-NDL} is NP-complete and study its parameterized complexity. In parameterized complexity, a problem is said to be fixed-parameter tractable with respect to a parameter if it has a solution whose running time is a function that is polynomial in the input size but possibly superpolynomial in the parameter. Golovach and Mertzios [ICSSR, 2016] studied editing to a graph with a given degree sequence and showed the problem is fixed-parameter tractable when parameterized by $\Delta+\ell$, where $\Delta$ is the maximum degree of the input graph and $\ell$ is the number of edits. We prove \textsc{Graph-Edit-to-NDL} is fixed-parameter tractable when parameterized by $\Delta+\ell$. Furthermore, we consider a harder problem \textsc{Constrained-Graph-Edit-to-NDL} (CGEN) that imposes constraints on the NDLs of intermediate graphs produced in the sequence. We adapt our FPT algorithm for \textsc{Graph-Edit-to-NDL} to solve \textsc{Constrained-Graph-Edit-to-NDL}, which proves \textsc{Constrained-Graph-Edit-to-NDL} is also fixed-parameter tractable when parameterized by $\Delta+\ell$. Our results imply that, for graph properties that can be expressed as properties of NDLs, editing to a graph with such a property is fixed-parameter tractable when parameterized by $\Delta+\ell$. We show that this family of graph properties includes some well-known graph measures used in complex network ana

关键词： Graph editing parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Design and Implementation of High Performance algorithms for the (n,k)-Universal Set Problem

Design and Implementation of High Performance Algorithms for...

引用

作者： Luo, Ping Texas A&M University

The k-path problem is to find a simple path of length k. This problem is NP-complete and has applications in bioinformatics for detecting signaling pathways in protein interaction networks and for biological subnetwork matching. There are algorithms implemented to solve the problem for k up to 13. The fastest implementation has running time O^*(4.32^k), which is slower than the best known algorithm of running time O^*(4^k). To implement the best known algorithm for the k-path problem, we need to construct (n,k)-universal set. In this thesis, we study the practical algorithms for constructing the (n,k)-universal set problem. We propose six algorithm variants to handle the increasing computational time and memory space needed for k=3, 4, ..., 8. We propose two major empirical techniques that cut the time and space tremendously, yet generate good results. For the case k=7, the size of the universal set found by our algorithm is 1576, and is 4611 for the case k=8. We implement the proposed algorithms with the OpenMP parallel interface and construct universal sets for k=3, 4, ..., 8. Our experiments show that our algorithms for the (n,k)-universal set problem exhibit very good parallelism and hence shed light on its MPI implementation. Ours is the first implementation effort for the (n,k)-universal set problem. We share the effort by proposing an extensible universal set construction and retrieval system. This system integrates universal set construction algorithms and the universal sets constructed. The sets are stored in a centralized database and an interface is provided to access the database easily. The (n,k)-universal set have been applied to many other NP-complete problems such as the set splitting problems and the matching and packing problems. The small (n,k)-universal set constructed by us will reduce significantly the time to solve those problems.

关键词： parameterized algorithms algorithms Engineering High Performance Computing Book Thesis

来源：评论

学校读者我要写书评

暂无评论

Strongly Connected Steiner Subgraphs with small number of Steiner vertices

Strongly Connected Steiner Subgraphs with small number of St...

引用

作者： Kemény, Tamás Dávid Charles University of Prague

Title: Strongly Connected Steiner Subgraphs with Small Number of Steiner Vertices Author: Tamás Dávid Kemény Department: Department of Applied Mathematics Supervisor: Dr. Andreas Emil Feldmann, Department of Applied Mathematics Abstract: Two well-established methods of dealing with hard optimization problems have been to develop approximation and parameterized algorithms. Recent results have shown that for some problems, it is only by combining these two approaches, into so-called pa- rameterized approximation algorithms, that we are able to efficiently find solutions that are of reasonable quality. This is the viewpoint from which we study the problem known as the Strongly Connected Steiner Subgraph problem, where a set of terminal vertices of an edge-weighted directed graph needs to be strongly-connected in the cheapest way possible. Keywords: Strongly Connected Steiner Subgraphs, parameterized algorithms, Approxi- mation algorithms, Bidirected Graphs iii

关键词： strongly-connected Steiner subgraphs parameterized algorithms approximation algorithms bidirected graphs

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：