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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

311 篇 期刊文献
70 篇 会议
2 篇 学位论文

馆藏范围

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

日期分布

学科分类号

237 篇 理学
- 234 篇 数学
- 4 篇 生物学
- 4 篇 统计学（可授理学、...
- 2 篇 物理学
234 篇 工学
- 193 篇 计算机科学与技术...
- 38 篇 软件工程
- 35 篇 电气工程
- 19 篇 信息与通信工程
- 8 篇 控制科学与工程
- 6 篇 机械工程
- 5 篇 电子科学与技术（可...
- 4 篇 土木工程
- 4 篇 交通运输工程
- 2 篇 动力工程及工程热...
- 1 篇 力学（可授工学、理...
- 1 篇 仪器科学与技术
- 1 篇 化学工程与技术
- 1 篇 石油与天然气工程
- 1 篇 生物工程
96 篇 管理学
- 96 篇 管理科学与工程(可...
- 17 篇 工商管理
- 1 篇 图书情报与档案管...
21 篇 经济学
- 17 篇 应用经济学
- 5 篇 理论经济学
2 篇 法学
- 2 篇 法学
1 篇 哲学
- 1 篇 哲学
1 篇 医学
- 1 篇 临床医学

主题

383 篇 polynomial-time ...
36 篇 computational co...
24 篇 np-completeness
17 篇 np-hardness
16 篇 np-hard
16 篇 scheduling
12 篇 np-complete
11 篇 dynamic programm...
10 篇 linear programmi...
10 篇 graph theory
9 篇 np-hard problem
9 篇 independent set
9 篇 combinatorial op...
8 篇 approximation al...
8 篇 stable matching
7 篇 discrete tomogra...
7 篇 matching
7 篇 complexity
6 篇 network
5 篇 temporal graph

机构

16 篇 univ warwick mat...
15 篇 univ warwick dim...
7 篇 rutgers state un...
7 篇 univ durham dept...
6 篇 univ glasgow dep...
6 篇 hong kong polyte...
6 篇 univ rostock ins...
5 篇 natl res univ hi...
4 篇 zhengzhou univ s...
4 篇 univ g dannunzio...
4 篇 kwansei gakuin u...
4 篇 natl res univ hi...
3 篇 univ ioannina de...
3 篇 univ glasgow sch...
3 篇 univ primorska u...
3 篇 kyoto univ grad ...
3 篇 russian acad sci...
3 篇 ben gurion univ ...
3 篇 univ wisconsin d...
3 篇 univ wisconsin w...

作者

15 篇 milanic martin
13 篇 lozin vadim
11 篇 lozin vadim v.
10 篇 manlove david f.
10 篇 malyshev d. s.
10 篇 miwa hiroyoshi
9 篇 mosca raffaele
7 篇 paulusma daniel
7 篇 brandstaedt andr...
7 篇 kobayashi yusuke
6 篇 mertzios george ...
6 篇 ries bernard
5 篇 purcell christop...
5 篇 van iersel leo
4 篇 lin lan
4 篇 gritzmann p
4 篇 maeda nao
4 篇 golovach petr a.
4 篇 del pia alberto
4 篇 papadopoulos cha...

语言

328 篇 英文
53 篇 其他
1 篇 土耳其文
1 篇 中文

检索条件"主题词=polynomial-time algorithm"

共 383 条记录，以下是321-330 订阅

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

详细简洁

排序：

On finding a solution in the core of a multicommodity flow game on a spider

On finding a solution in the core of a multicommodity flow g...

引用

IEEE Asia Pacific Conference on Circuits and Systems

作者： Yamada, Toshinori Karasawa, Kazuhiro Saitama Univ Grad Sch Sci & Engn Div Math Elect & Informat Sakura Ku 255 Shimo-Okubo Saitama 3388570 Japan

ISBN: (纸本)9781424403868

Motivated by the development of an effcient and stable routing scheme for the Internet, Papadimitriou introduced a multicommodity ow game and raised the problem of whether the core of a multicommodity ow game is always nonempty. Markakis and Saberi settled the problem affrmatively. However, thier proof is not constructive, and it is not known how to Ynd a solution in the core of the game, to the best of my knowledge. This paper presents a polynomial-time algorithm for nding pound a multicommodity ow game if G is a spider.

关键词： multicommodity flow game coalitional game core polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding edge-disjoint paths in partial k-trees 7th

Finding edge-disjoint paths in partial k-trees

引用

7th Annual International Symposium on algorithms and Computation

作者： Zhou, XA Tamura, S Nishizeki, T Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 98077 Japan

ISBN: (纸本)3540620486

For a given graph G and p pairs (s(i), t(i)), 1 less than or equal to i less than or equal to p, of vertices in G, the edge-disjoint paths problem is to find p pairwise edge-disjoint paths P-i 1 less than or equal to i less than or equal to p, connecting s(i) and t(i). Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by a fixed integer k), but it has not been known whether the edge-disjoint paths problem can be solved in polynomial time for partial k-trees unless p = O(1). This paper gives two algorithms for the edge-disjoint paths problem on partial k-trees. The first one solves the problem for any partial k-tree G and runs in polynomial time if p = O(log n) and in linear time if p = O(1), where n is the number of vertices in G. The second one solves the problem under some restriction on the location of terminal pairs even if p greater than or equal to log n.

关键词： edge-disjoint paths partial k-tree bounded tree-width polynomial-time algorithm edge-coloring

来源：评论

学校读者我要写书评

暂无评论

Variants of Graph Matching for Tree-like Graphs

Variants of Graph Matching for Tree-like Graphs

引用

2015 IEEE International Conference on Smart City/SocialCom/SustainCom (SmartCity)

作者： Nagoya, Takayuki Tottori Univ Environm Studies Gen Educ Ctr Tottori 6891111 Japan

ISBN: (纸本)9781509018932

Graphs can be effectively used to represent relationships between objects such as social networks, web search engines and genome sequencing. In this paper, we deal with two variants of graph matching, the graph isomorphism with restriction and the prefix set of graph isomorphism. We propose polynomial-time exact algorithms for these problems on graphs with tree-like structure. These could be useful tools for big data processing.

关键词： graph isomorphism with restriction partial k-trees polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Traffic Engineering by polynomially Solvable Link Metric Optimization

Traffic Engineering by Polynomially Solvable Link Metric Opt...

引用

1st International Conference on Intelligent Networking and Collaborative Systems

作者： Noguchi, Akira Fujimura, Takeshi Miwa, Hiroyoshi Kwansei Gakuin Univ Nishinomiya Hyogo 6691337 Japan

ISBN: (纸本)9781424451654

Open Shortest Path First (OSPF) is the most commonly used intra-domain internet routing protocol. As the routes of paths are determined by basically only the link metrics, many paths may pass a link with small metric;therefore, there is high possibility that it causes the congestion of the link. It is essential that the number of the paths with large traffic in a link is limited to avoid a congestion;therefore, it is important to determine the link metrics so as to limit the number of the paths in a link. In this paper, we define this link metric decision problem, and we prove that it is NP-complete. In addition, when we restricted this problem to determine the metric of only a link, we show that it can be solved in polynomial time.

关键词： OSPF shortest path NP-complete polynomial-time algorithm optimization problem

来源：评论

学校读者我要写书评

暂无评论

Maximum Independent Sets in Graphs of Low Degree 18

Maximum Independent Sets in Graphs of Low Degree

引用

18th ACM-SIAM Symposium on Discrete algorithms

作者： Lozin, Vadim Milanic, Martin Rutgers State Univ RUTCOR Piscataway NJ 08854 USA

We study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. In general, this problem is NP-hard. However, under certain restrictions it becomes polynomial-time solvable... 详细信息

ISBN: (纸本)9780898716245

关键词： Independent set NP-hardness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Independent domination in finitely defined classes of graphs: polynomial algorithms

Independent domination in finitely defined classes of graphs...

引用

8th International Colloquium on Graphs and Optimization (GO)

作者： Lozin, Vadim Mosca, Raffaele Purcell, Christopher Univ Warwick Inst Math Coventry CV4 7AL W Midlands England Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

We study the problem of finding in a graph an inclusionwise maximal independent set Of minimum cardinality, known as MINIMUM MAXIMAL INDEPENDENT SET or INDEPENDENT DOMINATING SET problem. This is one of the hardest problems in algorithmic graph theory. In particular, restricted to the class of so called SAT-graphs, this problem coincides with SATISFIABILITY, the central problem of theoretical computer science. The class of SAT-graphs, and many other important graph classes, such as graphs of bounded vertex degree or line graphs, can be characterized by finitely many forbidden induced subgraphs. We call such classes finitely defined. The paper [R. Boliac and V. Lozin, Independent domination in finitely defined classes of graphs, Theoretical Computer Science, 301 (2003) 271-284] reveals various conditions under which the INDEPENDENT DOMINATING SET problem remains NP-hard in a finitely defined class. In the present paper, we identify a number of finitely defined classes where the problem admits polynomial-time solutions. In particular, we prove that the problem is solvable in polynomial time in the class of P-2 + P-3-free graphs by correcting a mistake of the first two authors of the paper in their earlier solution. This result is in a sharp contrast with the fact that in the class of P-3 + P-3-free graphs the problem is known to be NP-hard, since this class contains all SAT-graphs. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Independent domination Finitely defined class of graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Combinatorics and algorithms for Quasi-chain Graphs 32nd

Combinatorics and Algorithms for Quasi-chain Graphs

引用

32nd International Workshop on Combinatorial algorithms (IWOCA)

作者： Alecu, Bogdan Atminas, Aistis Lozin, Vadim Malyshev, Dmitriy Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Xian Jiaotong Liverpool Univ Dept Math Sci 111 Renai Rd Suzhou 215123 Peoples R China Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Networks Anal 136 Rodionova Str Nizhnii Novgorod 603093 Russia Natl Res Lobachevsky State Univ Nizhny Novgorod 23 Gagarina Ave Nizhnii Novgorod 603950 Russia

ISBN: (纸本)9783030799878;9783030799861

The class of quasi-chain graphs is an extension of the well-studied class of chain graphs. The latter class enjoys many nice and important properties, such as bounded clique-width, implicit representation, well-quasi-ordering by induced subgraphs, etc. The class of quasi-chain graphs is substantially more complex. In particular, this class is not well-quasi-ordered by induced subgraphs, and the clique-width is not bounded in it. In the present paper, we show that the universe of quasi-chain graphs is at least as complex as the universe of permutations by establishing a bijection between the class of all permutations and a subclass of quasi-chain graphs. This implies, in particular, that the induced subgraph isomorphism problem is NP-complete for quasi-chain graphs. On the other hand, we propose a decomposition theorem for quasi-chain graphs that implies an implicit representation for graphs in this class and efficient solutions for some algorithmic problems that are generally intractable.

关键词： Bipartite chain graphs Implicit representation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial-time recognition of clique-width ≤ 3 graphs

Polynomial-time recognition of clique-width ≤ 3 graphs

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

作者： Corneil, Derek G. Habib, Michel Lanlignel, Jean-Marc Reed, Bruce Rotics, Udi Netanya Acad Coll Sch Math & Comp Sci IL-42100 Netanya Israel Univ Toronto Dept Comp Sci Toronto ON Canada UMR 7089 CNRS LIAFA F-75205 Paris 13 France Univ Paris 07 UFR Informat F-75205 Paris 13 France Univ Montpellier 2 LIRMM UMR CNRS F-34392 Montpellier 5 France McGill Univ Sch Comp Sci Canada Res Chair Combinator Complex Networks Montreal PQ Canada

Clique-width is a relatively new parameterization of graphs, philosophically similar to treewidth. Clique-width is more encompassing in the sense that a graph of bounded treewidth is also of bounded clique-width (but not the converse). For graphs of bounded clique-width, given the clique-width decomposition, every optimization, enumeration or evaluation problem that can be defined by a monadic second-order logic formula using quantifiers on vertices, but not on edges, can be solved in polynomial time. This is reminiscent of the situation for graphs of bounded treewidth, where the same statement holds even if quantifiers are also allowed on edges. Thus, graphs of bounded clique-width are a larger class than graphs of bounded treewidth, on which we can resolve fewer, but still many, optimization problems efficiently. One of the major open questions regarding clique-width is whether graphs of clique-width at most k, for fixed k, can be recognized in polynomial time. In this paper, we present the first polynomial-time algorithm (O(n(2)m)) to recognize graphs of clique-width at most 3. (C) 2012 Elsevier B.V. with parts of the article (C) Bruce Reed. All rights reserved.

关键词： Clique-width computation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal Scheduling of Urgent Preemptive Tasks

Optimal Scheduling of Urgent Preemptive Tasks

引用

16th IEEE International Conference on Embedded and Real-time Computing Systems and Applications (RTCSA)

作者： Andrei, Stefan Cheng, Albert Rinard, Martin Osborne, Lawrence Lamar Univ Dept Comp Sci Beaumont TX 77710 USA Univ Houston Dept Comp Sci Houston TX 77204 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

ISBN: (纸本)9780769541556

Tasks' scheduling has always been a central problem in the embedded real-time systems community. As in general the scheduling problem is NP-hard, researchers have been looking for efficient heuristics to solve the scheduling problem in polynomial time. One of the most important scheduling strategies is the Earliest Deadline First (EDF). It is known that EDF is optimal for uniprocessor platforms for many cases, such as: non-preemptive synchronous tasks (i.e., all tasks have the same starting time and cannot be interrupted), and preemptive asynchronous tasks (i.e., the tasks may be interrupted and may have arbitrary starting time). However, Mok showed that EDF is not optimal in multiprocessor platforms. In fact, for the multiprocessor platforms, the scheduling problem is NP-complete in most of the cases where the corresponding scheduling problem can be solved by a polynomial-time algorithm for uniprocessor platforms. Coffman and Graham identified a class of tasks for which the scheduling problem can be solved by a polynomial-time algorithm, that is, two-processor platform, no resources, arbitrary partial order relations, and every task is non-preemptive and has a unit computation time. Our paper introduces a new non-trivial and practical subclass of tasks, called urgent tasks. Briefly, a task is urgent if it is executed right after it is ready or it can only wait one unit time after it is ready. Practical examples of embedded real-time systems dealing with urgent tasks are all modern building alarm systems, as these include urgent tasks such as 'checking for intruders', 'sending a warning signal to the security office', 'informing the building's owner about a potential intrusion', and so on. By using propositional logic, we prove a new result in schedulability theory, namely that the scheduling problem for asynchronous and preemptive urgent tasks can be solved in polynomial time.

关键词： optimal scheduling urgent task polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Server Location Method for Keeping Shorter Distance from Users to Servers during Failures 6

Server Location Method for Keeping Shorter Distance from Use...

引用

2014 International Conference on Intelligent Networking and Collaborative Systems (IEEE INCoS 2014)

作者： Maeda, Nao Miwa, Hiroyoshi Kwansei Gakuin Univ Grad Sch Sci & Technol 2-1 Gakuen Sanda Hyogo 6691337 Japan

ISBN: (纸本)9781479963874

Recently, large contents in the Internet have increased loads of contents servers, networks and data centers, which may degrade the quality of services. To overcome this problem, some mirror servers providing the same contents are located on a network and a request is navigated to one of the mirror servers. A user must access to one of the servers and the hop length of a path from a user to a server should be short even during link failure. As it affects the performance, the location of the mirror servers is important. In this paper, we address the server location problem, which determines the location of the servers satisfying the following the constraint: any users can access servers within a small hop count even if some links fail. First, we formulate this problem and prove that it is NP-hard. Second, we present a polynomial-time algorithm for the case that the number of simultaneously failed links is restricted to one and the increase of the distance between a user node and servers during failure is restricted to be the number of nodes. Furthermore, we also present an approximation algorithm to solve this problem when the number of servers to be accessed is restricted to one and the number of simultaneously failed links is a constant positive integer, and we evaluate the performance by using some actual network topologies.

关键词： Network Graph theory Computation complexity Link failures Server location NP-hard polynomial-time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共39页 << < 29 30 31 32 33 34 35 36 37 38 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：