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

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Carmeli, Nofar Kenig, Batya Kimelfeld, Benny Technion Haifa Israel

ISBN: (纸本)9781450341981

We present an algorithm that enumerates all the minimal triangulations of a graph in incremental polynomial time. Consequently, we get an algorithm for enumerating all the proper tree decompositions, in incremental polynomial time, where "proper" means that the tree decomposition cannot be improved by removing or splitting a bag. The algorithm can incorporate any method for (ordinary, single result) triangulation or tree decomposition, and can serve as an anytime algorithm to improve such a method. We describe an extensive experimental study of an implementation on real data from different fields. Our experiments show that the algorithm improves upon central quality measures over the underlying tree decompositions, and is able to produce a large number of high-quality decompositions.

关键词： Minimal triangulation Tree decomposition enumeration algorithm Minimal separators Maximal independent sets Maximal cliques

来源：评论

学校读者我要写书评

暂无评论

Exploiting the Polyhedral Geometry of Stochastic Linear Bilevel Programming 24th

Exploiting the Polyhedral Geometry of Stochastic Linear Bile...

引用

24th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Munoz, Gonzalo Salas, David Svensson, Anton Univ OHiggins Inst Ciencias Ingenierfa Rancagua Chile

ISBN: (纸本)9783031327254;9783031327261

We study linear bilevel programming problems whose lower-level objective is given by a random cost vector with known distribution. We consider the case where this distribution is nonatomic, allowing to pose the problem of the leader using vertex-supported beliefs in the sense of [29]. We prove that, under suitable assumptions, this formulation turns out to be piecewise affine over the so-called chamber complex of the feasible set of the high point relaxation. We propose two algorithmic approaches to solve general problems enjoying this last property. The first one is based on enumerating the vertices of the chamber complex. The second one is a Monte-Carlo approximation scheme based on the fact that randomly drawn points of the domain lie, with probability 1, in the interior of full-dimensional chambers, where the problem (restricted to this chamber) can be reduced to a linear program.

关键词： Bilevel Programming Bayesian Approach Chamber complex enumeration algorithm Monte-Carlo algorithm

来源：评论

学校读者我要写书评

暂无评论

Generating all the minimal separators of a graph

引用

International Journal of Foundations of Computer Science 2000年第3期11卷 397-403页

作者： Berry, Anne Bordat, Jean-Paul Cogis, Olivier L.I.R.M.M. Laboratoire d'Informatique de Robotique et de Micro-électronique de Montpellier 34 392 Montpellier 161 Rue Ada France

We present an efficient algorithm which computes the set of minimal separators of a graph in O(n3) time per separator, thus gaining a factor of n2 on the current best-time algorithms for this problem. Our process is b... 详细信息

We present an efficient algorithm which computes the set of minimal separators of a graph in O(n³) time per separator, thus gaining a factor of n² on the current best-time algorithms for this problem. Our process is based on a new structural result, derived from the work of Kloks and Kratsch on listing all the minimal separators of a graph. © 2000 World Scientific Publishing Company.

关键词： enumeration algorithm Graph Minimal separator

来源：评论

学校读者我要写书评

暂无评论

On Euclid's algorithm and elementary number theory

On Euclid's algorithm and elementary number theory

引用

9th International Conference on Mathematics of Program Construction

作者： Backhouse, Roland Ferreira, Joao F. Univ Nottingham Sch Comp Sci Nottingham NG8 1BB England

algorithms can be used to prove and to discover new theorems. This paper shows how algorithmic skills in general, and the notion of invariance in particular, can be used to derive many results from Euclid's algorithm. We illustrate how to use the algorithm as a verification interface (i.e., how to verify theorems) and as a construction interface (i.e., how to investigate and derive new theorems). The theorems that we verify are well-known and most of them are included in standard number-theory books. The new results concern distributivity properties of the greatest common divisor and a new algorithm for efficiently enumerating the positive rationals in two different ways. One way is known and is due to Moshe Newman. The second is new and corresponds to a deforestation of the Stern-Brocot tree of rationals. We show that both enumerations stem from the same simple algorithm. In this way, we construct a Stern-Brocot enumeration algorithm with the same time and space complexity as Newman's algorithm. A short review of the original papers by Stern and Brocot is also included. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.

关键词： Number theory Calculational method Greatest common divisor Euclid's algorithm Invariant Eisenstein array Eisenstein-Stern tree (aka Calkin-Wilf tree) Stern-Brocot tree algorithm derivation enumeration algorithm Rational number

来源：评论

学校读者我要写书评

暂无评论

Computational determination of the largest lattice polytope diameter

引用

Electronic Notes in Discrete Mathematics 2017年 62卷 105-110页

作者： Chadder, Nathan Deza, Antoine Department of Computing and Software McMaster University Hamilton Canada

A lattice (d, k)-polytope is the convex hull of a set of points in dimension d whose coordinates are integers between 0 and k. Let δ(d,k) be the largest diameter over all lattice (d, k)-polytopes. We develop a computational framework to determine δ(d,k) for small instances. We show that δ(3,4)=7 and δ(3,5)=9;that is, we verify for (d,k)=(3,4) and (3, 5) the conjecture whereby δ(d,k) is at most ⌊(k+1)d/2⌋ and is achieved, up to translation, by a Minkowski sum of lattice vectors. © 2017 Elsevier B.V.

关键词： edge-graph diameter enumeration algorithm Lattice polytopes

来源：评论

学校读者我要写书评

暂无评论

The Maximum and Minimum Ant Colony Optimization Waking Strategy Based on Multi-Principle and Reprocessing 11th

The Maximum and Minimum Ant Colony Optimization Waking Strat...

引用

11th China Wireless Sensor Network Conference (CWSN)

作者： Wang Pengcheng Lin Tao Hebei Univ Technol Sch Comp Sci & Software Tianjin 300401 Peoples R China

ISBN: (纸本)9789811081231;9789811081224

The sensor's waking strategy is critical to the sensor network. The basic mathematical model of waking strategy is TSP problem. Some typical intelligent algorithms for TSP problem model include ant colony algorithm, genetic algorithm and so on. On the basis of the maximum and minimum ant colony algorithm, this paper improves the following disadvantages: According to the principle of choosing the city based on the pheromone principle, the non-contract principle is added, The principle of city selection and make it in the process of selecting the city, the priority to follow the principle of non-contract;in a single path after the help of the enumeration algorithm with the special advantages, refer to the enumeration algorithm part of the results of the re-processing of the path, The path can cover the search space. The improved algorithm avoids the occurrence of stagnation to a certain extent, weakening the blindness of search. The possibility of the results is increased by 25%, single results of the calculation time is reduced by 89.79%.

关键词： Maximum and minimum ant colony algorithm Optimization algorithm enumeration algorithm Traveling salesman problem Intelligent algorithm Waking strategy

来源：评论

学校读者我要写书评

暂无评论

Enumerating Possible Seedings in a Knockout Tournament 5

Enumerating Possible Seedings in a Knockout Tournament

引用

5th International Conference on Computer Science and Engineering (UBMK)

作者： Atilgan, Can Dalkilic, Mehmet Emin Ege Univ Int Comp Inst Izmir Turkey

ISBN: (纸本)9781728175652

A knockout tournament, also known as an elimination tournament is a very common competition scheme where competitors play a one-versus-one game with the loser eliminated from the competition and the winner advancing to the next round until there is only one competitor left. The setting of the first round of games called "seeding" naturally influences the competition. Although there is considerable amount of work in the literature on how to seed a knockout tournament to achieve some objectives, an algorithm to enumerate possible knockout tournament seedings has not been explicitly presented to the best of our knowledge. In this paper, a discussion on counting the number of possible seedings in a knockout tournament and an algorithm for effectively enumerating the seedings are proposed.

关键词： Knockout tournament seeding enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Towards Characterizing The Solution Space Of The 1-Dollo Phylogeny Problem

Towards Characterizing The Solution Space Of The 1-Dollo Phy...

引用

作者： Shunping Xie University of Illinois – Urbana-Champaign

学位级别：硕士

Cancer cells may mutate multiple times, from a normal state to a mutated state and vice versa. Given our sequenced data, we can model the mutation process with a phylogenetic tree. One representative model is the k-Dollo parsimony, where all observed mutations mutate from a single normal cell and each character of a cell is gained at most once and lost at most k times. We examine the 1-Dollo Phylogeny problem, does a 1-Dollo phylogeny, a tree that follows the 1-Dollo parsimony model, exist for the observations. Current algorithms to solve the 1-Dollo Phylogeny problem only tell us whether or not a set of observations has a 1-Dollo phylogeny by outputting a single solution. We explore the structure of 1-Dollo phylogenies and use our idea of a skeleton to develop an algorithm that enumerates all 1-Dollo phylogenies for any set of observations. This algorithm runs much faster than the naive brute force enumeration algorithm for random input. The implementation is here: https://***/sxie12/skeleton_solver.

关键词： 1-Dollo phylogeny Skeleton enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Gene bi-targeting by viral and human miRNAs

引用

BMC BIOINFORMATICS 2010年第1期11卷 1-17页

作者： Veksler-Lublinsky, Isana Shemer-Avni, Yonat Kedem, Klara Ziv-Ukelson, Michal Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

Background: MicroRNAs (miRNAs) are an abundant class of small noncoding RNAs (20-24 nts) that can affect gene expression by post-transcriptional regulation of mRNAs. They play important roles in several biological processes (e. g., development and cell cycle regulation). Numerous bioinformatics methods have been developed to identify the function of miRNAs by predicting their target mRNAs. Some viral organisms also encode miRNAs, a fact that contributes to the complex interactions between viruses and their hosts. A need arises to understand the functional relationship between viral and host miRNAs and their effect on viral and host genes. Our approach to meet this challenge is to identify modules where viral and host miRNAs cooperatively regulate host gene expression. Results: We present a method to identify groups of viral and host miRNAs that cooperate in post-transcriptional gene regulation, and their target genes that are involved in similar biological processes. We call these groups (genes and miRNAs of human and viral origin) - modules. The modules are found in a new two-stage procedure, which we call bi-targeting, and is presented in this paper. The stages are (i) a new and efficient target prediction, and (ii) a new method for clustering objects of three different data types. In this work we integrate multiple information sources, including miRNA-target binding information, miRNA expression profiles, and GO annotations. Our hypotheses and the methods have been tested on human and Epstein Barr virus (EBV) miRNAs and human genes, for which we found 34 modules. We provide supporting evidence from biological and medical literature for two of our modules. Our code and data are available at http://***/similar to vaksler/*** Conclusions: The presented algorithm, which makes use of diverse biological data, is demonstrated to be an efficient approach for finding bi-targeting modules of viral and human miRNAs. These modules can contribute to a

关键词： Gene Ontology Epstein Barr Virus Target Prediction enumeration algorithm Human miRNAs

来源：评论

学校读者我要写书评

暂无评论

Globally optimal synthesis of heat exchanger networks. Part I: Minimal networks

引用

AICHE JOURNAL 2020年第7期66卷 e162667-e162667页

作者： Chang, Chenglin Peccini, Alice Wang, Yufei Costa, Andre L. H. Bagajewicz, Miguel J. China Univ Petr State Key Lab Heavy Oil Proc Beijing Peoples R China Zhejiang Univ Coll Chem & Biol Engn Zhejiang Prov Key Lab Adv Chem Engn Manufacture T Hangzhou Peoples R China Rio de Janeiro State Univ UERJ Inst Chem Rio De Janeiro Brazil Univ Oklahoma Sch Chem Biol & Mat Engn Norman OK 73019 USA

This article introduces the concept of minimal structure (MSTR) and presents an enumeration algorithm for the synthesis of heat exchanger networks based on MSTR. Minimal Structures refer to a class of heat exchanger networks featuring acyclic heat transfer networks without energy loops. The enumerations used are either exhaustive or smart with a stopping criterion. Without loss of generality we use the isothermal mixing Synheat model, that is, the method applies identically to other superstructures, with likely variations in the optimization models associated to each step. A conjecture is used to state that the algorithm renders solutions that are globally optimal. Literature examples are used to demonstrate the capabilities of the enumeration algorithm. Most of our solutions compare favorably with the best reported ones in literature, with exceptions where the reported solution is not minimal.

关键词： enumeration algorithm global optimality heat exchanger networks minimal structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：