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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

42 篇 期刊文献
14 篇 会议

馆藏范围

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

日期分布

学科分类号

48 篇 工学
- 46 篇 计算机科学与技术...
- 16 篇 软件工程
- 1 篇 机械工程
- 1 篇 生物工程
34 篇 理学
- 32 篇 数学
- 2 篇 生物学
5 篇 管理学
- 5 篇 管理科学与工程(可...
- 2 篇 工商管理
2 篇 经济学
- 2 篇 应用经济学
1 篇 法学
- 1 篇 法学

主题

56 篇 fpt algorithms
10 篇 parameterized co...
7 篇 kernelization
4 篇 exponential time...
4 篇 treewidth
3 篇 computational co...
3 篇 dominating set
3 篇 kernel lower bou...
3 篇 chordal graphs
3 篇 vertex cover
3 篇 planar graphs
3 篇 parameterized al...
3 篇 steiner tree
3 篇 np-completeness
2 篇 path-width
2 篇 branch-width
2 篇 tandem duplicati...
2 篇 fixed parameter ...
2 篇 binary decision ...
2 篇 edge contraction...

机构

5 篇 montana state un...
4 篇 univ bergen dept...
3 篇 cispa helmholtz ...
3 篇 univ bergen berg...
3 篇 univ montpellier...
3 篇 inst math sci ma...
2 篇 int inst informa...
2 篇 nihon univ
2 篇 univ maryland de...
2 篇 univ perugia dep...
2 篇 univ bergen dept...
2 篇 inst math sci ch...
2 篇 ben gurion univ ...
2 篇 chinese acad sci...
2 篇 hbni inst math s...
2 篇 univ sherbrooke ...
2 篇 max planck inst ...
1 篇 weizmann inst sc...
1 篇 indian inst tech...
1 篇 indian inst sci ...

作者

6 篇 zhu binhai
6 篇 saurabh saket
4 篇 tale prafullkuma...
4 篇 marx daniel
3 篇 ashok pradeesha
3 篇 silva ana
3 篇 van 't hof pim
3 篇 lopes raul
3 篇 golovach petr a.
3 篇 didimo walter
3 篇 zou peng
2 篇 heggernes pinar
2 篇 iwata yoichi
2 篇 li wenjun
2 篇 koebler johannes
2 篇 toda seinosuke
2 篇 gupta naman
2 篇 kolay sudeshna
2 篇 villanger yngve
2 篇 de figueiredo ce...

语言

53 篇 英文
3 篇 其他

检索条件"主题词=FPT Algorithms"

共 56 条记录，以下是41-50 订阅

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

详细简洁

排序：

Parameterized Complexity of MAXIMUM EDGE COLORABLE SUBGRAPH 26th

Parameterized Complexity of MAXIMUM EDGE COLORABLE SUBGRAPH

引用

26th International Computing and Combinatorics Conference (COCOON)

作者： Agrawal, Akanksha Kundu, Madhumita Sahu, Abhishek Saurabh, Saket Tale, Prafullkumar Ben Gurion Univ Negev Beer Sheva Israel Indian Stat Inst Kolkata India HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

ISBN: (纸本)9783030581503;9783030581497

A graph H is p-edge colorable if there is a coloring phi: E(H) -> {1, 2,...,p}, such that for distinct uv, vw is an element of E(H), we have phi(uv) not equal phi(vw). The MAXIMUM EDGE-COLORABLE SUBGRAPH problem takes as input a graph G and integers l and p, and the objective is to find a subgraph H of G and a p-edge-coloring of H, such that vertical bar E(H)vertical bar >= l. We study the above problem from the viewpoint of Parameterized Complexity. We obtain fpt algorithms when parameterized by: (1) the vertex cover number of G, by using INTEGER LINEAR PROGRAMMING, and (2) 1, a randomized algorithm via a reduction to RAINBOW MATCHING, and a deterministic algorithm by using color coding, and divide and color. With respect to the parameters p+k, where k is one of the following: (1) the solution size, 1, (2) the vertex cover number of G, and (3) l - mm(G), where mm(G) is the size of a maximum matching in G;we show that the (decision version of the) problem admits a kernel with O(k . p) vertices. Furthermore, we show that there is no kernel of size O(k(1-is an element of). f (p)), for any is an element of > 0 and computable function f, unless NP subset of coNP/poly.

关键词： Edge coloring Kernelization fpt algorithms Kernel lower bound

来源：评论

学校读者我要写书评

暂无评论

The Tandem Duplication Distance Is NP-Hard 37

The Tandem Duplication Distance Is NP-Hard

引用

37th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Lafond, Manuel Zhu, Binhai Zou, Peng Univ Sherbrooke Dept Comp Sci Sherbrooke PQ J1K 2R1 Canada Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA Montana State Univ Gianforte Sch Comp Bozeman MT 59717 USA

ISBN: (纸本)9783959771405

In computational biology, tandem duplication is an important biological phenomenon which can occur either at the genome or at the DNA level. A tandem duplication takes a copy of a genome segment and inserts it right after the segment - this can be represented as the string operation AXB double right arrow AXXB. Tandem exon duplications have been found in many species such as human, fly or worm, and have been largely studied in computational biology. The Tandem Duplication (TD) distance problem we investigate in this paper is defined as follows: given two strings S and T over the same alphabet, compute the smallest sequence of tandem duplications required to convert S to T. The natural question of whether the TD distance can be computed in polynomial time was posed in 2004 by Leupold et al. and had remained open, despite the fact that tandem duplications have received much attention ever since. In this paper, we prove that this problem is NP-hard, settling the 16-year old open problem. We further show that this hardness holds even if all characters of S are distinct. This is known as the exemplar TD distance, which is of special relevance in bioinformatics. One of the tools we develop for the reduction is a new problem called the Cost-Effective Subgraph, for which we obtain W[1]-hardness results that might be of independent interest. We finally show that computing the exemplar TD distance between S and T is fixed-parameter tractable. Our results open the door to many other questions, and we conclude with several open problems.

关键词： Tandem duplication Text processing Formal languages Computational genomics fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Decremental Sensitivity Oracles for Covering and Packing Minors 41

Decremental Sensitivity Oracles for Covering and Packing Min...

引用

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

作者： Kanesh, Lawqueen Panolan, Fahad Ramanujan, M. S. Strulo, Peter Indian Inst Technol Jodhpur Jodhpur India Univ Leeds Sch Comp Leeds England Univ Warwick Warwick England

ISBN: (纸本)9783959773119

In this paper, we present the first decremental fixed-parameter sensitivity oracles for a number of basic covering and packing problems on graphs. In particular, we obtain the first decremental sensitivity oracles for VERTEX PLANARIZATION (delete k vertices to make the graph planar) and CYCLE PACKING (pack k vertex-disjoint cycles in the given graph). That is, we give a sensitivity oracle that preprocesses the given graph in time f (k, f)n(9(1) such that, when given a set of edge deletions, the data structure decides in time f (k, l)n(O(1)) whether the updated graph is a positive instance of the problem. These results are obtained as a corollary of our central result, which is the first decremental sensitivity oracle for TOPOLOGICAL MINOR DELETION (cover all topological minors in the input graph that belong to a specified set, using k vertices). Though our methodology closely follows the literature, we are able to produce the first explicit bounds on the preprocessing and query times for several problems. We also initiate the study of fixed-parameter sensitivity oracles with so-called structural parameterizations and give sufficient conditions for the existence of fixed-parameter sensitivity oracles where the parameter is just the treewidth of the graph. In contrast, all existing literature on this topic and the aforementioned results in this paper assume a bound on the solution size (a weaker parameter than treewidth for many problems). As corollaries, we obtain decremental sensitivity oracles for well-studied problems such as VERTEX COVER and DOMINATING SET when only the treewidth of the input graph is bounded. A feature of our methodology behind these results is that we are able to obtain query times independent of treewidth.

关键词： Sensitivity oracles Data Structures fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized and Approximation algorithms for the Maximum Bimodal Subgraph Problem 31st

Parameterized and Approximation Algorithms for the Maximum B...

引用

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

作者： Didimo, Walter Fomin, Fedor V. Golovach, Petr A. Inamdar, Tanmay Kobourov, Stephen Sieper, Marie Diana Univ Perugia Dept Engn Perugia Italy Univ Bergen Dept Comp Sci Bergen Norway Univ Arizona Dept Comp Sci Tucson AZ 85721 USA Univ Wurzburg Dept Comp Sci Wurzburg Germany

ISBN: (纸本)9783031492747;9783031492754

A vertex of a plane digraph is bimodal if all its incoming edges (and hence all its outgoing edges) are consecutive in the cyclic order around it. A plane digraph is bimodal if all its vertices are bimodal. Bimodality is at the heart of many types of graph layouts, such as upward drawings, level-planar drawings, and L-drawings. If the graph is not bimodal, the Maximum Bimodal Subgraph (MBS) problem asks for an embedding-preserving bimodal subgraph with the maximum number of edges. We initiate the study of the MBS problem from the parameterized complexity perspective with two main results: (i) we describe an fpt algorithm parameterized by the branchwidth (and hence by the treewidth) of the graph;(ii) we establish that MBS parameterized by the number of non-bimodal vertices admits a polynomial kernel. As the byproduct of these results, we obtain a subexponential fpt algorithm and an efficient polynomial-time approximation scheme for MBS.

关键词： bimodal graphs maximum bimodal subgraph parameterized complexity fpt algorithms polynomial kernel approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Adapting The Directed Grid Theorem into an fpt Algorithm 10th

Adapting The Directed Grid Theorem into an FPT Algorithm

引用

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

作者： Campos, Victor Lopes, Raul Maia, Ana Karolinna Sau, Ignasi Univ Fed Cear ParGO Grp Fortaleza Ceara Brazil Univ Montpellier LIRMM CNRS Montpellier France

Originally proved in 1986 by Robertson and Seymour, the Grid Theorem is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem isn directed graphs was conjectured by Johnson et al. in 2001, and proved recently by Kawarabayashi and Kreutzer in 2015. Namely they showed that there is a function f (k) such that every directed graph of directed tree-width at least f (k) contains a cylindrical grid of size k as a butterfly minor. Moreover, they claim that their proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor. In this article, we adapt some of the steps of the proof of Kawarabayashi and Kreutzer and we improve the XP algorithm into an fpt algorithm. The first step of the proof is an XP algorithm by Johnson et al. in 2001 that decides whether a directed graph D has directed tree-width at most 3k - 2 or admits a haven of order k. It is worth mentioning that a skecth of an fpt algorithm for this problem appears in Chapter 9 of the book "Classes of Directed Graphs", from 2018, with an approximation factor of 5k + 2. Our first contribution is to adapt the proof from Johnson et al. to find either an arboreal decomposition of width at most 3k - 2 or a haven of order k in a directed graph D in fpt time by making use of important separators. We then follow the roadmap of the proof by Kawarabayashi and Kreutzer by locally improving the complexity at some steps, in particular concerning the problem of finding hitting sets for brambles of large order.

关键词： Directed graphs directed tree-width grid theorem fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Parameterized algorithms for Steiner Tree and Dominating Set: Bounding the Leafage by the Vertex Leafage 16th

Parameterized Algorithms for Steiner Tree and Dominating Set...

引用

16th International Conference and Workshops on algorithms and Computation

作者： de Figueiredo, Celina M. H. Lopes, Raul de Melo, Alexsander A. Silva, Ana Univ Fed Rio de Janeiro Rio De Janeiro Brazil Univ Fed Ceara Fortaleza Ceara Brazil

ISBN: (纸本)9783030967307;9783030967314

Chordal graphs are intersection graphs of subtrees of a tree, while interval graphs are intersection graphs of subpaths of a path. Undirected path graphs are an intermediate class of graphs, defined as the intersection graphs of paths of a tree. It is known that Dominating Set, Connected Dominating Set, and Steiner Tree are W[2]-hard on chordal graphs, when parameterized by the size of the solution, and are polynomial-time solvable on interval graphs. As for the undirected path graphs, all these problems are known to be NP-complete, and when parameterized by the size of the solution, no classification in the parameterized complexity theory is known apart from the trivial XP classification. We prove that Dominating Set, Connected Dominating Set, and Steiner Tree are fpt for undirected path graphs when parameterized by the size of the solution, and that they continue to be fpt for general chordal graphs when parameterized by the size of the solution plus the vertex leafage of the graph, provided a tree model with optimal vertex leafage is given. We show a relation between the parameterization of Min-LC-VSP problems by the leafage of the graph versus the vertex leafage plus the size of a solution.

关键词： Chordal graphs Undirected Path graphs Dominating Set Steiner Tree fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Combinatorial algorithms in machine learning 1

Combinatorial algorithms in machine learning

引用

1st IEEE International Conference on Artificial Intelligence for Industries (AI4I)

作者： Shaw, Peter Massey Univ Manawatu Sch Engn & Adv Technol Palmerston North New Zealand

ISBN: (纸本)9781538692097

Although quite old, the classic data clustering problem strives to segment the data into homogeneous groupings where homogeneity is measured by, for example, Gini Index. Classical techniques strive to group the data, by what one would argue as "smart" trial-and-error procedure. I will show how data could be clustered using entirely combinatorial techniques where Gini Index or Mean Squared Error receive no mention whatsoever. The Cluster-Editing algorithm aka "Edit-Distance" shows a great promise to help solve those intractable high-dimensional problems because it's totally indifferent to the dimensionality of the data.

关键词： Machine Learning high dimensional data dimensionality reduction fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

On the k-colored Rainbow Sets in Fixed Dimensions 15th

On the <i>k</i>-colored Rainbow Sets in Fixed Dimensions

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Keikha, Vahideh Keikha, Hamidreza Mohades, Ali Czech Acad Sci Inst Comp Sci Vodarenskou Vezi 2 Prague 18207 Czech Republic Amirkabir Univ Technol Dept Comp Engn Tehran Iran Amirkabir Univ Technol Dept Math & Comp Sci Tehran Iran

ISBN: (纸本)9783030926816;9783030926809

In this paper, we introduce a variant of the minimum diameter color spanning set (MDCSS) problem. Let P be a set of n points of m colors in R-d. For a given k, our objective is to find a set with k points of different colors that admits the minimum possible diameter. Such a set is called a k-rainbow set. This problem has applications in database queries, mostly composed by weighted points (i.e., a positive value is assigned to each point as its weight), and seeking a maximum weight k-rainbow set. We first assume the points have equal weight and design an fpt algorithm, which we generalize to the weighted version. We also solve the decision and the enumeration version of the problem by introducing a reduction to all maximal independent sets of a bipartite graph. We also introduce a 1.154-approximation algorithm for this problem and a 2.236-approximation for the enumeration version, and we perform some experimental studies on a real data-set, as well as providing several analyses of the data-set based on the outputs of our algorithm. Our exact algorithms and the approximation algorithm for the enumeration problem have a complexity being near-linear to n in R-2.

关键词： Minimum diameter color spanning set fpt algorithms Colored points

来源：评论

学校读者我要写书评

暂无评论

Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games

Finding Optimal Strategies of Almost Acyclic Simple Stochast...

引用

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

作者： Auger, David Coucheney, Pierre Strozecki, Yann Univ Versailles St Quentin En Yvelines PRiSM Versailles France

ISBN: (纸本)9783319060897;9783319060880

The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the few problems in NP boolean AND coNP which are not known to be in P. However, there are some cases where these games can be easily solved, as for instance when the underlying graph is acyclic. In this work, we try to extend this tractability to several classes of games that can be thought as "almost" acyclic. We give some fixed-parameter tractable or polynomial algorithms in terms of different parameters such as the number of cycles or the size of the minimal feedback vertex set.

关键词： algorithmic game theory stochastic games fpt algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimum Conflict Free Colouring Parameterized by Treewidth 6th

Minimum Conflict Free Colouring Parameterized by Treewidth

引用

6th International Conference on algorithms and Discrete Applied Mathematics

作者： Ashok, Pradeesha Bhargava, Rathin Gupta, Naman Khalid, Mohammad Yadav, Dolly Int Inst Informat Technol Bangalore Bangalore Karnataka India Indian Inst Sci Educ & Res Mohali Mohali India

ISBN: (纸本)9783030392185;9783030392192

Conflict free q-Colouring of a graph G refers to the colouring of a subset of vertices of G using q colours such that every vertex has a neighbour of unique colour. In this paper, we study the MINIMUM CONFLICT FREE Q-COLOURING problem. Given a graph G and a fixed constant q, MINIMUM CONFLICT FREE Q-Colouring is to find a Conflict free q-Colouring of G that minimises the number of coloured vertices. We study the MINIMUM CONFLICT FREE Q-COLOURING problem parameterized by the treewidth of G. We give an fpt algorithm for this problem and also prove running time lower bounds under Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH).

关键词： Conflict free colouring of graphs Parameterized complexity fpt algorithms Treewidth Exponential Time Hypothesis Strong Exponential Time Hypothesis

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共6页 << < 1 2 3 4 5 6 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：