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

您好，读者！请登录

内蒙古大学图书馆

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

咨询与建议

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

您的常用邮箱：*

您的手机号码：*

问题描述：

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

分类表

所选分类

>> <<

限定检索结果

文献类型

195 篇 期刊文献
125 篇 会议

馆藏范围

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

日期分布

学科分类号

246 篇 理学
- 235 篇 数学
- 20 篇 统计学（可授理学、...
- 16 篇 系统科学
- 13 篇 物理学
- 4 篇 化学
- 4 篇 生物学
- 3 篇 地球物理学
169 篇 工学
- 123 篇 计算机科学与技术...
- 78 篇 软件工程
- 37 篇 土木工程
- 34 篇 建筑学
- 23 篇 测绘科学与技术
- 17 篇 材料科学与工程（可...
- 11 篇 信息与通信工程
- 11 篇 控制科学与工程
- 10 篇 电子科学与技术（可...
- 5 篇 电气工程
- 4 篇 农业工程
- 3 篇 机械工程
- 3 篇 光学工程
- 3 篇 化学工程与技术
- 3 篇 生物医学工程（可授...
- 3 篇 生物工程
- 2 篇 轻工技术与工程
- 2 篇 林业工程
30 篇 管理学
- 18 篇 图书情报与档案管...
- 13 篇 管理科学与工程(可...
- 5 篇 工商管理
4 篇 法学
- 4 篇 社会学
4 篇 农学
- 4 篇 作物学
1 篇 经济学
1 篇 教育学

主题

24 篇 parameterization
18 篇 graph theory
14 篇 polynomial appro...
12 篇 graphic methods
11 篇 trees (mathemati...
11 篇 parameter estima...
9 篇 approximation al...
9 篇 directed graphs
8 篇 drawing (graphic...
8 篇 computational co...
7 篇 hamiltonians
7 篇 visualization
7 篇 constraint satis...
5 篇 encoding (symbol...
5 篇 computational ge...
5 篇 optimization
4 篇 undirected graph...
4 篇 machine learning
4 篇 clustering algor...
4 篇 polynomials

机构

227 篇 algorithms and c...
17 篇 department of in...
16 篇 department of co...
13 篇 algorithms and c...
9 篇 indian institute...
8 篇 school of comput...
6 篇 faculty of infor...
5 篇 school of comput...
5 篇 school of comput...
5 篇 department of in...
5 篇 department of ap...
5 篇 department of ma...
4 篇 university of le...
4 篇 department of en...
4 篇 department of en...
4 篇 institute of inf...
4 篇 institute of mat...
4 篇 algorithms and c...
4 篇 algorithms and c...
4 篇 cispa helmholtz ...

作者

85 篇 ganian robert
69 篇 nöllenburg marti...
47 篇 szeider stefan
31 篇 eiben eduard
31 篇 bhore sujoy
27 篇 ordyniak sebasti...
18 篇 simonov kirill
17 篇 hamm thekla
17 篇 klute fabian
16 篇 ramanujan m.s.
14 篇 kanj iyad
14 篇 montecchiani fab...
13 篇 wallinger markus
12 篇 golovach petr a.
12 篇 li guangping
12 篇 wulms jules
12 篇 fomin fedor v.
11 篇 rutter ignaz
9 篇 gronemann martin
9 篇 villedieu anaïs

语言

304 篇 英文
15 篇 其他

检索条件"机构=Algorithms and complexity group"

共 320 条记录，以下是21-30 订阅

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

详细简洁

排序：

An algorithmic study of fully dynamic independent sets for map labeling 28

An algorithmic study of fully dynamic independent sets for m...

引用

28th Annual European Symposium on algorithms, ESA 2020

作者： Bhore, Sujoy Li, Guangping Nöllenburg, Martin Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959771627

Map labeling is a classical problem in cartography and geographic information systems (GIS) that asks to place labels for area, line, and point features, with the goal to select and place the maximum number of independent, i.e., overlap-free, labels. A practically interesting case is point labeling with axis-parallel rectangular labels of common size. In a fully dynamic setting, at each time step, either a new label appears or an existing label disappears. Then, the challenge is to maintain a maximum cardinality subset of pairwise independent labels with sub-linear update time. Motivated by this, we study the maximal independent set (MIS) and maximum independent set (Max-IS) problems on fully dynamic (insertion/deletion model) sets of axis-parallel rectangles of two types – (i) uniform height and width and (ii) uniform height and arbitrary width;both settings can be modeled as rectangle intersection graphs. We present the first deterministic algorithm for maintaining a MIS (and thus a 4-approximate Max-IS) of a dynamic set of uniform rectangles with amortized sub-logarithmic update time. This breaks the natural barrier of Ω(∆) update time (where ∆ is the maximum degree in the graph) for vertex updates presented by Assadi et al. (STOC 2018). We continue by investigating Max-IS and provide a series of deterministic dynamic approximation schemes. For uniform rectangles, we first give an algorithm that maintains a 4-approximate Max-IS with O(1) update time. In a subsequent algorithm, we establish the trade-off between approximation quality 2(1 + k1 ) and update time O(k2 log n), for k ∈ N. We conclude with an algorithm that maintains a 2-approximate Max-IS for dynamic sets of unit-height and arbitrary-width rectangles with O(ω log n) update time, where ω is the maximum size of an independent set of rectangles stabbed by any horizontal line. We have implemented our algorithms and report the results of an experimental comparison exploring the trade-off between solution qu

关键词： Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Relative Efficiency of Dynamic and Static Top-Down Compilation to Decision-DNNF 27

On the Relative Efficiency of Dynamic and Static Top-Down Co...

引用

27th International Conference on Theory and Applications of Satisfiability Testing, SAT 2024

作者： de Colnet, Alexis Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773348

Top-down compilers of CNF formulas to circuits in decision-DNNF (Decomposable Negation Normal Form) have proved to be useful for model counting. These compilers rely on a common set of techniques including DPLL-style exploration of the set of models, caching of residual formulas, and connected components detection. Differences between compilers lie in the variable selection heuristics and in the additional processing techniques they may use. We investigate, from a theoretical perspective, the ability of top-down compilation algorithms to find small decision-DNNF circuits for two different variable selection strategies. Both strategies are guided by a graph of the CNF formula and are inspired by what is done in practice. The first uses a dynamic graph-partitioning approach while the second works with a static tree decomposition. We show that the dynamic approach performs significantly better than the static approach for some formulas, and that the opposite also holds for other formulas. Our lower bounds are proved despite loose settings where the compilation algorithm is only forced to follow its designed variable selection strategy and where everything else, including the many opportunities for tie-breaking, can be handled non-deterministically. © Alexis de Colnet.

关键词： Program compilers

来源：评论

学校读者我要写书评

暂无评论

Separating Incremental and Non-Incremental Bottom-Up Compilation 26

Separating Incremental and Non-Incremental Bottom-Up Compila...

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

作者： De Colnet, Alexis Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772860

The aim of a compiler is, given a function represented in some language, to generate an equivalent representation in a target language L. In bottom-up (BU) compilation of functions given as CNF formulas, constructing the new representation requires compiling several subformulas in L. The compiler starts by compiling the clauses in L and iteratively constructs representations for new subformulas using an "Apply" operator that performs conjunction in L, until all clauses are combined into one representation. In principle, BU compilation can generate representations for any subformulas and conjoin them in any way. But an attractive strategy from a practical point of view is to augment one main representation - which we call the core - by conjoining to it the clauses one at a time. We refer to this strategy as incremental BU compilation. We prove that, for known relevant languages L for BU compilation, there is a class of CNF formulas that admit BU compilations to L that generate only polynomial-size intermediate representations, while their incremental BU compilations all generate an exponential-size core. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Program compilers

来源：评论

学校读者我要写书评

暂无评论

Proven Optimally-Balanced Latin Rectangles with SAT 29

Proven Optimally-Balanced Latin Rectangles with SAT

引用

29th International Conference on Principles and Practice of Constraint Programming, CP 2023

作者： Ramaswamy, Vaidyanathan Peruvemba Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773003

Motivated by applications from agronomic field experiments, Díaz, Le Bras, and Gomes [CPAIOR 2015] introduced Partially Balanced Latin Rectangles as a generalization of Spatially Balanced Latin Squares. They observed that the generation of Latin rectangles that are optimally balanced is a highly challenging computational problem. They computed, utilizing CSP and MIP encodings, Latin rectangles up to 12 × 12, some optimally balanced, some suboptimally balanced. In this paper, we develop a SAT encoding for generating balanced Latin rectangles. We compare experimentally encoding variants. Our results indicate that SAT encodings perform competitively with the MIP encoding, in some cases better. In some cases we could find Latin rectangles that are more balanced than previously known ones. This finding is significant, as there are many arithmetic constraints involved. The SAT approach offers the advantage that we can certify that Latin rectangles are optimally balanced through DRAT proofs that can be verified independently. © Vaidyanathan Peruvemba Ramaswamy and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

SAT modulo symmetries for graph generation 27

SAT modulo symmetries for graph generation

引用

27th International Conference on Principles and Practice of Constraint Programming, CP 2021

作者： Kirchweger, Markus Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772112

We propose a novel constraint-based approach to graph generation. Our approach utilizes the interaction between a CDCL SAT solver and a special symmetry propagator where the SAT solver runs on an encoding of the desired graph property. The symmetry propagator checks partially generated graphs for minimality w.r.t. a lexicographic ordering during the solving process. This approach has several advantages over a static symmetry breaking: (i) symmetries are detected early in the generation process, (ii) symmetry breaking is seamlessly integrated into the CDCL procedure, and (iii) the propagator can perform a complete symmetry breaking without causing a prohibitively large initial encoding. We instantiate our approach by generating extremal graphs with certain restrictions in terms of girth and diameter. With our approach, we could confirm the Simon-Murty Conjecture (1979) on diameter-2-critical graphs for graphs up to 18 vertices. © Markus Kirchweger and Stefan Szeider.

关键词： Encoding (symbols)

来源：评论

学校读者我要写书评

暂无评论

Structure-Guided Local Improvement for Maximum Satisfiability 30

Structure-Guided Local Improvement for Maximum Satisfiabilit...

引用

30th International Conference on Principles and Practice of Constraint Programming, CP 2024

作者： Schidler, André Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959773362

The enhanced performance of today's MaxSAT solvers has elevated their appeal for many large-scale applications, notably in software analysis and computer-aided design. Our research delves into refining anytime MaxSAT solving by repeatedly identifying and solving with an exact solver smaller subinstances that are chosen based on the graphical structure of the instance. We investigate various strategies to pinpoint these subinstances. This structure-guided selection of subinstances provides an exact solver with a high potential for improving the current solution. Our exhaustive experimental analyses contrast our methodology as instantiated in our tool MaxSLIM with previous studies and benchmark it against leading-edge MaxSAT solvers. © André Schidler and Stefan Szeider.

关键词： graphical structure incomplete MaxSAT large neighborhood search (LNS) maximum satisfiability metaheuristic SAT-based local improvement (SLIM)

来源：评论

学校读者我要写书评

暂无评论

A SAT Solver's Opinion on the Erdos-Faber-Lovász Conjecture 26

A SAT Solver's Opinion on the Erdos-Faber-Lovász Conjecture

引用

26th International Conference on Theory and Applications of Satisfiability Testing, SAT 2023

作者： Kirchweger, Markus Peitl, Tomas Szeider, Stefan Algorithms and Complexity Group TU Wien Austria

ISBN: (纸本)9783959772860

In 1972, Paul Erdos, Vance Faber, and Lászlo Lovász asked whether every linear hypergraph with n vertices can be edge-colored with n colors, a statement that has come to be known as the EFL conjecture. Erdos himself considered the conjecture as one of his three favorite open problems, and offered increasing money prizes for its solution on several occasions. A proof of the conjecture was recently announced, for all but a finite number of hypergraphs. In this paper we look at some of the cases not covered by this proof. We use SAT solvers, and in particular the SAT Modulo Symmetries (SMS) framework, to generate non-colorable linear hypergraphs with a fixed number of vertices and hyperedges modulo isomorphisms. Since hypergraph colorability is NP-hard, we cannot directly express in a propositional formula that we want only non-colorable hypergraphs. Instead, we use one SAT (SMS) solver to generate candidate hypergraphs modulo isomorphisms, and another to reject them by finding a coloring. Each successive candidate is required to defeat all previous colorings, whereby we avoid having to generate and test all linear hypergraphs. Computational methods have previously been used to verify the EFL conjecture for small hypergraphs. We verify and extend these results to larger values and discuss challenges and directions. Ours is the first computational approach to the EFL conjecture that allows producing independently verifiable, DRAT proofs. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Set theory

来源：评论

学校读者我要写书评

暂无评论

Solving problems on graphs of high rank-width 14th

Solving problems on graphs of high rank-width

引用

14th International Symposium on algorithms and Data Structures, WADS 2015

作者： Eiben, Eduard Ganian, Robert Szeider, Stefan Algorithms and Complexity Group Institute of Computer Graphics and Algorithms TU Wien Vienna Austria

ISBN: (纸本)9783319218397

A modulator of a graph G to a specified graph class H is a set of vertices whose deletion puts G into H. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain FPT algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are strictly more general than the cardinality of modulators and rank-width itself. Then, we develop an FPT algorithm for finding such well-structured modulators to any graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for MINIMUM VERTEX COVER and MAXIMUM CLIQUE. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for efficiently deciding problems expressible in Monadic Second Order (MSO) logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

MaxSAT-Based Postprocessing for Treedepth 26th

MaxSAT-Based Postprocessing for Treedepth

引用

26th International Conference on Principles and Practice of Constraint Programming, CP 2020

作者： Peruvemba Ramaswamy, Vaidyanathan Szeider, Stefan Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030584740

Treedepth is an increasingly popular graph invariant. Many NP-hard combinatorial problems can be solved efficiently on graphs of bounded treedepth. Since the exact computation of treedepth is itself NP-hard, recent research has focused on the development of heuristics that compute good upper bounds on the treedepth. In this paper, we introduce a novel MaxSAT-based approach for improving a heuristically obtained treedepth decomposition. At the core of our approach is an efficient MaxSAT encoding of a weighted generalization of treedepth arising naturally due to subtree contractions. The encoding is applied locally to the given treedepth decomposition to reduce its depth, in conjunction with the collapsing of subtrees. We show the local improvement method’s correctness and provide an extensive experimental evaluation with some encouraging results. © 2020, Springer Nature Switzerland AG.

关键词： Forestry

来源：评论

学校读者我要写书评

暂无评论

Minimizing crossings in constrained two-sided circular graph layouts 34

Minimizing crossings in constrained two-sided circular graph...

引用

34th International Symposium on Computational Geometry, SoCG 2018

作者： Klute, Fabian Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783959770668

Circular layouts are a popular graph drawing style, where vertices are placed on a circle and edges are drawn as straight chords. Crossing minimization in circular layouts is NP-hard. One way to allow for fewer crossings in practice are two-sided layouts that draw some edges as curves in the exterior of the circle. In fact, one- and two-sided circular layouts are equivalent to one-page and two-page book drawings, i.e., graph layouts with all vertices placed on a line (the spine) and edges drawn in one or two distinct half-planes (the pages) bounded by the spine. In this paper we study the problem of minimizing the crossings for a fixed cyclic vertex order by computing an optimal k-plane set of exteriorly drawn edges for k > 1, extending the previously studied case k = 0. We show that this relates to finding bounded-degree maximum-weight induced subgraphs of circle graphs, which is a graph-theoretic problem of independent interest. We show NP-hardness for arbitrary k, present an efficient algorithm for k = 1, and generalize it to an explicit XP-time algorithm for any fixed k. For the practically interesting case k = 1 we implemented our algorithm and present experimental results that confirm the applicability of our algorithm. © Fabian Klute and Martin Nöllenburg;licensed under Creative Commons License CC-BY 34th Symposium on Computational Geometry (SoCG 2018).

关键词： Drawing (graphics)

来源：评论

学校读者我要写书评

暂无评论

没有更多数据了...

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

共32页 << < 1 2 3 4 5 6 7 8 9 10 > >>

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

隐藏清空

合并搜索

回到顶部

执行限定条件

内容：

评分：

请选择保存的检索档案：

请选择收藏分类：

订阅名称：

通借通还

温馨提示：

图书名称：

借书校区：

取书校区：

手机号码：

邮箱地址：

一卡通帐号：

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

联系人：

所在院系：

联系邮箱：

联系电话：

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

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：