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

International Conference on Industrial Control and Electronics Engineering (ICICEE)

作者： Zhu Ning-hong Gong Shang-Fu Xian Univ Sci & Technol Coll Comp Sci & Technol Xian Peoples R China

ISBN: (纸本)9780769547923

Based on the study of enumeration algorithm, the paper proposes the multi-parameter setting method in enumeration algorithm parameter values to achieve operation independence of parameters. That is: in order to achieve the independence of variable values, and in order to facilitate program design, if there were m variables in enumeration algorithm and each variable may have n states, the value of the n states could be set at a geometric sequence, the ratio of which is not less than m+1. Generally choose to use 1, m +1, (m +1)(2) ... (m +1) (n-1) of the geometric progression.

关键词： enumeration algorithm the independence of parameters multiple loop geometric progression parameter setting

来源：评论

学校读者我要写书评

暂无评论

Block Palindromes: A New Generalization of Palindromes 1

引用

25th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Goto, Keisuke Tomohiro, I. Bannai, Hideo Inenaga, Shunsuke Fujitsu Labs Ltd Kawasaki Kanagawa Japan Kyushu Inst Technol Iizuka Fukuoka Japan Kyushu Univ Fukuoka Fukuoka Japan

ISBN: (数字)9783030004798

ISBN: (纸本)9783030004798;9783030004781

We study a new generalization of palindromes and gapped palindromes called block palindromes. A block palindrome is a string that becomes a palindrome when identical substrings are replaced with a distinct character. We investigate several properties of block palindromes and in particular, study substrings of a string which are block palindromes. In so doing, we introduce the notion of a maximal block palindrome, which leads to a compact representation of all block palindromes that occur in a string. We also propose an algorithm which enumerates all maximal block palindromes that appear in a given string T in O(vertical bar T vertical bar + parallel to MBP(T)parallel to) time, where parallel to MBP(T)parallel to is the output size, which is optimal unless all the maximal block palindromes can be represented in a more compact way.

关键词： Palindrome enumeration algorithm Factorization

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Frontier-Based Search for Enumerating All Constrained Subgraphs with Compressed Representation

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2017年第9期E100A卷 1773-1784页

作者： Kawahara, Jun Inoue, Takeru Iwashita, Hiroaki Minato, Shin-ichi Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300192 Japan NTT Corp NTT Network Innovat Labs Yokosuka Kanagawa 2390847 Japan Fujitsu Labs Ltd Kawasaki Kanagawa 2118588 Japan Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan

For subgraph enumeration problems, very efficient algorithms have been proposed whose time complexities are far smaller than the number of subgraphs. Although the number of subgraphs can exponentially increase with the input graph size, these algorithms exploit compressed representations to output and maintain enumerated subgraphs compactly so as to reduce the time and space complexities. However, they are designed for enumerating only some specific types of subgraphs, e.g., paths or trees. In this paper, we propose an algorithm framework, called the frontier-based search, which generalizes these specific algorithms without losing their efficiency. Our frontier-based search will be used to resolve various practical problems that include constrained subgraph enumeration.

关键词： zero-suppressed binary decision diagram froniter-based search enumeration algorithm subgraph

来源：评论

学校读者我要写书评

暂无评论

Realistic roofs without local minimum edges over a rectilinear polygon

引用

THEORETICAL COMPUTER SCIENCE 2017年 675卷 15-26页

作者： Yoon, Sang Duk Ahn, Hee-Kap Sherette, Jessica POSTECH Dept Comp Sci & Engn Pohang South Korea Univ Texas San Antonio Dept Comp Sci San Antonio TX USA

Computing all possible roofs over a given ground plan is a common task in automatically reconstructing a three dimensional building. In 1995, Aichholzer et al. proposed a definition of a roof over a simple polygon P in the xy-plane as a terrain over P whose faces are supported by planes containing edges of P and making a dihedral angle pi/4 with the xy-plane. This definition, however, allows roofs with faces isolated from the boundary of P and local minimum edges inducing pools of rainwater. Very recently, Ahn et al. introduced "realistic roofs" over a rectilinear polygon with n vertices by imposing two additional constraints under which no isolated faces and no local minimum vertices are allowed. Their definition is, however, restricted and excludes a number of roofs with no local minimum edges. In this paper, we propose a new definition of realistic roofs over a rectilinear polygon that corresponds to the class of roofs without isolated faces and local minimum edges. We investigate the geometric and combinatorial properties of realistic roofs and show that the maximum possible number of distinct realistic roofs over a rectilinear n-gon is at most 1.3211(m) ((left perpendicular m/2 right perpendicular) (m)), where m = (n-4)/2. We also present two algorithms that generate all realistic roofs. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Realistic roof enumeration algorithm Computational geometry

来源：评论

学校读者我要写书评

暂无评论

algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 81卷 203-215页

作者： Rosa, Bruno Ferreira Freitas Souza, Marcone Jamilson de Souza, Sergio Ricardo de Franca Filho, Moacir Felizardo Ales, Zacharie Paul Michelon, Philippe Yves Fed Ctr Technol Educ Minas Gerais CEFET MG BR-30510000 Belo Horizonte MG Brazil Fed Univ Ouro Preto UFOP Dept Comp Sci BR-35400000 Ouro Preto MG Brazil Univ Avignon & Pays de Vaucluse LIA EA 4128 F-84911 Avignon France

This paper addresses the single machine scheduling problem with distinct time windows and sequence dependent setup times. The objective is to minimize the total weighted earliness and tardiness. The problem involves determining the job execution sequence and the starting time for each job in the sequence. An implicit enumeration algorithm denoted IE and a general variable neighborhood search algorithm denoted GVNS are proposed to determine the job scheduling. IE is an exact algorithm, whereas GVNS is a heuristic algorithm. In order to define the starting times, an O(n(2)) idle time insertion algorithm (ITIA) is proposed. IE and GVNS use the ITIA algorithm to determine the starting time for each job. However, the IE algorithm is only valid for instances with sequence -independent setup times, and takes advantage of theoretical results generated for this problem. Computational experiments show that the ITIA algorithm is more efficient than the only other equivalent algorithm found in the literature. The IE algorithm allows the optimal solutions of all instances with up to 15 jobs to be determined within a feasible computational time. For larger instances, GVNS produces better-quality solutions requiring less computational time compared with the other algorithm from the literature. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Makespan Idle time enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

On the exact solution of the no-wait flow shop problem with due date constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2017年第May期81卷 141-159页

作者： Samarghandi, Hamed Behroozi, Mehdi Univ Saskatchewan Edwards Sch Business Dept Finance & Management Sci Saskatoon SK S7N 5A7 Canada Northeastern Univ Dept Mech & Ind Engn 334 Snell Engn Ctr360 Huntington Ave Boston MA 02115 USA

This paper deals with the no-wait flow shop scheduling problem with due date constraints. In the no wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, the jobs should be completed before their respective due dates;due date constraints are dealt with as hard constraints. The considered performance criterion is makespan. The problem is strongly NP-hard. This paper develops a number of distinct mathematical models for the problem based on different decision variables. Namely, a mixed integer programming model, two quadratic mixed integer programming models, and two constraint programming models are developed. Moreover, a novel graph representation is developed for the problem. This new modeling technique facilitates the investigation of some of the important characteristics of the problem;this results in a number of propositions to rule out a large number of infeasible solutions from the set of all possible permutations. Afterward, the new graph representation and the resulting propositions are incorporated into a new exact algorithm to solve the problem to optimality. To investigate the performance of the mathematical models and to compare them with the developed exact algorithm, a number of test problems are solved and the results are reported. Computational results demonstrate that the developed algorithm is significantly faster than the mathematical models. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： No-wait flow shop Due date constraints Mixed integer programming Constraint programming enumeration algorithm

来源：评论

学校读者我要写书评

暂无评论

Linear-time algorithm for generating c-isolated bicliques

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2017年第8期94卷 1574-1590页

作者： Alamgir, Zareen Karim, Saira Husnine, Syed Natl Univ Comp & Emerging Sci Dept Comp Sci Block B Lahore Pakistan Natl Univ Comp & Emerging Sci Dept Math Lahore Pakistan

Bicliques are widely used to solve various real-world problems encountered in bio-informatics, data mining and networks. We consider c-isolated bicliques, a variation of bicliques. The c-isolated bicliques can model communities in social and biological networks. We propose an efficient algorithm to generate all c-isolated maximal bicliques in a given bipartite graph. Our algorithm exploits underlying properties of an isolated biclique to trim the input graph. Furthermore, the algorithm deploys the vertex cover enumeration algorithm based on fixed parameter tractability and lists all maximal c-isolated bicliques in linear time (in terms of graph size), for constant c.

关键词： Combinatorial algorithm enumeration algorithm biclique isolated biclique graph algorithms 68R10 68Q25 90C35 05C69

来源：评论

学校读者我要写书评

暂无评论

Exact Computation of Influence Spread by Binary Decision Diagrams 17

Exact Computation of Influence Spread by Binary Decision Dia...

引用

26th International Conference on World Wide Web (WWW)

作者： Maehara, Takanori Suzuki, Hirofumi Ishihata, Masakazu Shizuoka Univ Shizuoka Japan RIKEN Ctr Adv Intelligence Project Tokyo Japan Hokkaido Univ Sapporo Hokkaido Japan

ISBN: (纸本)9781450349130

Evaluating influence spread in social networks is a fundamental procedure to estimate the word-of-mouth effect in viral marketing. There are enormous studies about this topic;however, under the standard stochastic cascade models, the exact computation of influence spread is known to be #P-hard. Thus, the existing studies have used Monte-Carlo simulation-based approximations to avoid exact computation. We propose the first algorithm to compute influence spread exactly under the independent cascade model. The algorithm first constructs binary decision diagrams (BDDs) for all possible realizations of influence spread, then computes influence spread by dynamic programming on the constructed BDDs. To construct the BDDs efficiently, we designed a new frontier-based search-type procedure. The constructed BDDs can also be used to solve other influence-spread related problems, such as random sampling without rejection, conditional influence spread evaluation, dynamic probability update, and gradient computation for probability optimization problems. We conducted computational experiments to evaluate the proposed algorithm. The algorithm successfully computed influence spread on real-world networks with a hundred edges in a reasonable time, which is quite impossible by the naive algorithm. We also conducted an experiment to evaluate the accuracy of the Monte-Carlo simulation-based approximation by comparing exact influence spread obtained by the proposed algorithm.

关键词： viral marketing influence spread enumeration algorithm binary decision diagram

来源：评论

学校读者我要写书评

暂无评论

Efficiently Enumerating Minimal Triangulations 17

Efficiently Enumerating Minimal Triangulations

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：