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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

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

详细简洁

排序：

Min-max coverage problems on tree-like metrics 12

Min-max coverage problems on tree-like metrics

引用

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

作者： Aaron, Eric Hebert-Johnson, Ursula Krizanc, Danny Lokshtanov, Daniel Colby Coll Waterville ME 04901 USA Univ Calif Santa Barbara Santa Barbara CA 93106 USA Wesleyan Univ Middletown CT 06457 USA

We consider a number of min-max coverage problems. In each problem, the input is an unweighted graph G and an integer k, and possibly some additional information, such as a root vertex r. In the MIN-MAX Path Cover problem, the task is to cover all vertices of the graph by k walks, minimizing the length of the longest walk. The variant of MIN-MAX Path Cover in which all walks start and end at the same prescribed root vertex r is called the k-TRAVELING SALESMEN PROBLEM. In the MIN-MAX TREE COVER problem, the task is to cover all vertices of the graph by k trees, minimizing the size (number of edges) of the largest tree. In the rooted version, MIN-MAX k-ROOTED TREE COVER, the input also contains k roots r(1), . . . , r(k), and the ith tree must contain the root r(i). These four problems are all known to be APX-hard and to admit a constant-factor approximation. In this paper, we initiate the systematic study of these problems on trees and, more generally, on graphs of constant treewidth. As opposed to most graph problems, all four of the above coverage problems remain NP-hard even when G is a tree. We obtain an n(O(k))-time exact algorithm for all four problems on graphs of bounded treewidth. Our main contribution is a quasi-polynomial-time approximation scheme (QPTAS) for the k-TRAVELING SALESMEN PROBLEM, MIN-MAX PATH COVER, and MIN-MAX TREE COVER on graphs of bounded treewidth.(C) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (https://***/licenses/by-nc-nd/4.0)

关键词： Approximation algorithms parameterized algorithms Min-max coverage Treewidth Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite Tournaments

A Quadratic Vertex Kernel for Feedback Arc Set in Bipartite ...

引用

37th International Symposium on Mathematical Foundations of Computer Science, (MFCS)

作者： Xiao, Mingyu Guo, Jiong Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Univ Saarland D-66123 Saarbrucken Germany

ISBN: (纸本)9783642325892;9783642325885

The k-feedback arc set problem is to determine whether there is a set F of at most k arcs in a directed graph G such that the removal of F makes G acyclic. The k-feedback arc set problems in tournaments and bipartite tournaments (k-FAST and k-FASBT) have applications in ranking aggregation and have been extensively studied from the viewpoint of parameterized complexity. Recently, Misra et al. provide a problem kernel with O(k(3)) vertices for k-FASBT. Answering an open question by Misra et al., we improve the kernel bound to O(k(2)) vertices by introducing a new concept called "bimodule."

关键词： Kernelization Feedback arc set Bipartite tournament Graph algorithms parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Kernelization for Graph Packing Problems via Rainbow Matching 34

Kernelization for Graph Packing Problems via Rainbow Matchin...

引用

34th ACM-SIAM Annual Symposium on Discrete algorithms (SODA)

作者： Bessy, Stephane Bougeret, Marin Thilikos, Dimitrios M. Wiederrecht, Sebastian Univ Montpellier CNRS LIRMM Montpellier France Inst for Basic Sci Korea Discrete Math Grp Daejeon South Korea

ISBN: (纸本)9781611977554

We introduce a new kernelization tool, called rainbow matching technique, that is appropriate for the design of polynomial kernels for packing problems. Our technique capitalizes on the powerful combinatorial results of [Graf, Harris, Haxell, SODA 2021]. We apply the rainbow matching technique on two (di)graph packing problems, namely the Triangle-Packing in Tournament problem (TPT), where we ask for a packing of k directed triangles in a tournament, and the Induced 2-Path-Packing (I2PP) where we ask for a packing of k induced paths of length two in a graph. The existence of a sub-quadratic kernels for these problems was proven for the first time in [Fomin, Le, Lokshtanov, Saurabh, Thomasse, Zehavi. ACM Trans. algorithms, 2019], where they gave a kernel of O(k(3/2)) vertices and O(k(5/3)) vertices respectively. In the same paper it was questioned whether these bounds can be (optimally) improved to linear ones. Motivated by this question, we apply the rainbow matching technique and prove that TPT admits an (almost linear) kernel of k(1+ O(1)/root log k) vertices and that I2PP admits a kernel of O(k) vertices.

关键词： Kernelization parameterized algorithms Rainbow matching Packing problems

来源：评论

学校读者我要写书评

暂无评论

Packing paths: Recycling saves time

Packing paths: Recycling saves time

引用

9th Cologne/Twente Workshop on Graphs and Combinatorial Optimization (CTW)

作者： Binkele-Raible, Daniel Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany

We consider packing problems in graphs under a parameterized perspective. Starting from a maximal path packing P of size j we use extremal arguments for determining how many vertices of P appear in a path packing of size j + 1. Generally, one can re-use 2j vertices of j paths of length three, four and five. This is improved to 3j, 2.5j and 3j vertices. (c) 2013 Published by Elsevier B.V.

关键词： parameterized algorithms Graphs Packings Extremal graph theory

来源：评论

学校读者我要写书评

暂无评论

Colorful Graph Coloring

Colorful Graph Coloring

引用

3rd International Joint Conference on Theoretical Computer Science (IJTCS) / 16th International Conference on Frontiers of Algorithmic Wisdom (FAW)

作者： Zhang, Zhongyi Guo, Jiong Shandong Univ Sch Comp Sci & Technol Jinan Peoples R China

ISBN: (纸本)9783031207952;9783031207969

Given a simple graph G and a positive integer d, the Colorful Graph Coloring problem (CGC) asks for the minimum number of colors needed to color the "coloring elements" of G, such that for every "colorful element" of G, the coloring elements in its "neighborhood" have at least d colors. Both coloring elements and colorful elements of G can be vertices and edges, which means that there are four variants of CGC. With both coloring and colorful elements being vertices, we use Vertex-Coloring Vertex-Colorful (VCVC) to denote the variant of CGC, which asks for the minimum number of colors needed to color the vertices such that for every vertex v, the vertices in the closed neighborhood of v are colored by at least d colors. The Vertex-Coloring Edge-Colorful variant (VCEC) colors the vertices such that every edge is incident to vertices of at least d colors. Clearly, this variant is meaningful only for d <= 2 with simple graphs as input, and with d = 2 is equivalent to the classical Graph Coloring problem. The Edge-Coloring Vertex-Colorful variant (ECVC) demands for every vertex v that the edges incident to v are colored by at least d colors. Finally, the Edge-Coloring Edge-Colorful variant (ECEC) colors the edges such that the "closed neighborhood" of every edge contains d distinctly colored edges. The closed neighborhood of an edge e contains e and all edges sharing endpoints with e. Motivated by the extensive research on Graph Coloring and the applications of Colorful Graph Coloring in resource allocation, we initialize the complexity study of VCVC, ECVC, and ECEC and achieve the following results. VCVC is polynomial-time solvable for d <= 2 and becomes NP-hard for d >= 3. We also present a parameterized algorithm for VCVC with treewidth as parameter. ECVC is NP-hard only in the case that d is set equal to the minimum degree of vertices delta(G). If d not equal delta(G), then ECVC is polynomial-time solvable. Based on this, we show that in the case of d = delta(G), we

关键词： Graph coloring NP-hard Absolute approximation parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Exact and Approximate Pattern Counting in Degenerate Graphs: New algorithms, Hardness Results, and Complexity Dichotomies 62

Exact and Approximate Pattern Counting in Degenerate Graphs:...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bressan, Marco Roth, Marc Univ Milan Dept Comp Sci Milan Italy Univ Oxford Dept Comp Sci Oxford England Univ Oxford Merton Coll Oxford England

ISBN: (纸本)9781665420556

We study the problems of counting the homomorphisms, the copies, and the induced copies of a k-vertex graph H in a d-degenerate n-vertex graph G. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance, we show that the copies of H in G can be counted in time f(k, d)n(max(1,imn(H))) log n, where f is some computable function and imn(H) is the size of the largest induced matching of H;and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time f(k, d) n(o(imn(H)/ log imn(H))) for any function f, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number alpha(H) in place of imn(H). These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when d is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as k-matchings and k-trees, in d-degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i.e., counting patterns with a given property) in degenerate graphs.

关键词： counting problems degenerate graphs fine-grained complexity theory parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Block-graph width

Block-graph width

引用

6th International Conference on Theory and Application of Models of Computation (TAMC 09)

作者： Chang, Maw-Shang Hung, Ling-Ju Kloks, Ton Peng, Sheng-Lung Natl Dong Hwa Univ Dept Comp Sci & Informat Engn Hualien 97401 Taiwan Natl Chung Cheng Univ Dept Comp Sci & Informat Engn Chiayi 62107 Taiwan

ISBN: (纸本)9783642020162

Let g, be a class of graphs. A graph G has g-width k if there are k independent sets N-1,...,N-k in G such that G can be embedded into a graph H is an element of g, such that for every edge e in H which is not an edge in G, there exists an i such that both endvertices of e are in N-i. For the class B of block graphs we show that graphs with B-width at most 4 are perfect. We also show that B-width is NP-complete and show that it is fixed-parameter tractable. For the class C. of complete graphs, similar results are also obtained. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Probe graphs parameterized algorithms Block graphs

来源：评论

学校读者我要写书评

暂无评论

algorithms for Circuits and Circuits for algorithms

Algorithms for Circuits and Circuits for Algorithms

引用

IEEE 29th Conference on Computational Complexity (CCC)

作者： Williams, Ryan Stanford Univ Dept Comp Sci Stanford CA 94305 USA

ISBN: (纸本)9781479936267

The title of this paper is meant to highlight an emerging duality between two fundamental topics in algorithms and complexity theory. algorithms for circuits refers to the design of interesting algorithms which can perform non-trivial circuit analysis of some kind, on either a circuit or a Boolean function given as a truth table. For instance, an algorithm determining whether a given circuit has an input that forces a true output would solve the NP-complete Circuit-SAT problem. Such an algorithm is of course unlikely to run in polynomial time, but could possibly be more efficient than exhaustively trying all possible inputs to the circuit. Circuits for algorithms refers to the modeling of uniform algorithms with non-uniform circuit families (or proving such modeling is impossible). For instance, the NEXP versus P/poly question asks whether nondeterministic exponential-time algorithms can be simulated using non-uniform circuit families of polynomial size. It is widely believed that the answer is no, however the present mathematical tools available are still too crude to prove this kind of separation. This paper surveys these two generic subjects, the ways in which they arise, and connections that have been developed between them, focusing on the connections between nontrivial circuit-analysis algorithms and proofs of circuit size lower bounds. To give one example, if there is a nontrivial algorithm (running slightly faster than exhaustive search) that can determine if a given circuit computes a constant function, then it can be concluded that NEXP is not contained in P/poly. Informally, this connection can be interpreted as saying "some good algorithms for circuits imply there are no good circuits for some algorithms."

关键词： satisfiability derandomization exact algorithms learning circuit complexity parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Tractable QBF by Knowledge Compilation 36

Tractable QBF by Knowledge Compilation

引用

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

作者： Capelli, Florent Mengel, Stefan Univ Lille INRIA UMR 9189 CRIStALCtr Rech Informat Signal & Automat Lille F-59000 Lille France CRIL CNRS UMR 8188 Lens France

ISBN: (纸本)9783959771009

We generalize several tractability results concerning the tractability of Quantified Boolean Formulas (QBF) with restricted underlying structure. To this end, we introduce a notion of width for structured DNNF which are a class of Boolean circuits heavily studied in knowledge compilation, a subarea of artificial intelligence. We then show that structured DNNF allow quantifier elimination with a size blow-up depending only on the width of the DNNF and not its size. Using known algorithms transforming restricted CNF-formulas into deterministic DNNF, we apply this result to generalize several results for counting and decision on QBF. We also complement these results with lower bounds that show that our definitions and results are essentially optimal in several senses.

关键词： QBF knowledge compilation parameterized algorithms

来源：评论

学校读者我要写书评

暂无评论

Polynomial Kernels for Deletion to Classes of Acyclic Digraphs 33

Polynomial Kernels for Deletion to Classes of Acyclic Digrap...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Mnich, Matthias van Leeuwen, Erik Jan Univ Bonn Bonn Germany Max Planck Inst Informat Saarbrucken Germany

ISBN: (纸本)9783959770019

We consider the problem to find a set X of vertices (or arcs) with vertical bar X vertical bar <= k in a given digraph G such that D = G - X is an acyclic digraph. In its generality, this is DIRECTED FEEDBACK VERTEX SET or DIRECTED FEEDBACK ARC SET respectively. The existence of a polynomial kernel for these problems is a notorious open problem in the field of kernelization, and little progress has been made. In this paper, we consider both deletion problems with an additional restriction on D, namely that D must be an out-forest, an out-tree, or a (directed) pumpkin. Our main results show that for each of these three restrictions the vertex deletion problem remains N P-hard, but we can obtain a kernel with k(O)(1) vertices on general digraphs G. We also show that, in contrast to the vertex deletion problem, the arc deletion problem with each of the above restrictions can be solved in polynomial time.

关键词： directed feedback vertex/arc set parameterized algorithms kernels

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

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

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：