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

Diameter Constrained Fuzzy Minimum Spanning Tree Problem

INTERNATIONAL JOURNAL OF COMPUTATIONAL INTELLIGENCE SYSTEMS 2013年第6期6卷 1040-1051页

作者： Abu Nayeem, Sk. Md. Pal, Madhumangal Aliah Univ Dept Math Kolkata 700091 W Bengal India Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 W Bengal India

In this paper, we have studied the constrained version of the fuzzy minimum spanning tree problem. Costs of all the edges are considered as fuzzy numbers. Using the m(lambda) measure, a generalization of credibility measure, the problem is formulated as chance-constrained programming problem and dependent-chance programming problem according to different decision criteria. Then the crisp equivalents are derived when the fuzzy costs are characterized by trapezoidal fuzzy numbers. Furthermore, a fuzzy simulation based hybrid genetic algorithm is designed to solve the proposed models using prufer like code representation of labeled trees.

关键词： Minimum spanning tree possibility and necessity measure chance constrained programming prufer code genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Unified parallel encoding and decoding algorithms for Dandelion-like codes

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2010年第11期70卷 1119-1127页

作者： Caminiti, Saverio Petreschi, Rossella Univ Roma La Sapienza Dept Comp Sci I-00198 Rome Italy

The Dandelion-like codes are eight bijections between labeled trees and strings of node labels. The literature contains optimal sequential algorithms for these bijections, but no parallel algorithms have been reported. In this paper the first parallel encoding and decoding algorithms for Dandelion-like codes are presented. Namely, a unique encoding algorithm and a unique decoding algorithm, which when properly parameterized, can be used for all Dandelion-like codes, are designed. These algorithms are optimal in the sequential setting. The encoding algorithm implementation on an EREW PRAM is optimal, while the efficient implementation of the decoding algorithm requires concurrent reading. (c) 2010 Elsevier Inc. All rights reserved.

关键词： Bijective tree encoding prufer code Dandelion-like codes PRAM algorithms

来源：评论

学校读者我要写书评

暂无评论

The Dandelion code: A new coding of spanning trees for genetic algorithms

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2007年第1期11卷 91-100页

作者： Thompson, Evan Paulden, Tim Smith, David K. UK Dept Work & Pens London WC2A 2LS England Univ Exeter Dept Math Sci Exeter EX4 4QE Devon England

There are many applications where it is necessary to find an optimal spanning tree. For several of these, recent research has suggested the use of genetic algorithms (GAs). Historically, the prufer code has been one of the most popular representations for spanning trees, due largely to the bijective mapping between genotype and phenotype. However, it is has attracted much criticism for its low locality, a primary reason for its poor performance in GAs. Other representations such as direct encoding and network random keys have been shown to be far more effective. In 2001, an alternative called the Blob code was identified and adapted for use in GAs. It was shown to exhibit significantly higher locality than the prufer code. For a simple test problem, a GA using the Blob code was found to substantially outperform one using the prufer code. This paper suggests an alternative called the Dandelion code, which is more efficient and exhibits yet higher locality. Although both direct encoding and NetKeys are shown to give better results on the test problems used in this paper, the Dandelion code should be considered as a strong alternative, particularly for very large networks.

关键词： Blob code Dandelion code encoding genetic algorithms (GAs) one-max-tree problem optimal communication spanning tree (OCST) problem prufer code prufer string representation spanning trees

来源：评论

学校读者我要写书评

暂无评论

Multifactorial evolutionary algorithm for solving clustered tree problems: competition among Cayley codes Case studies on the clustered shortest-path tree problem and the minimum inter-cluster routing cost clustered tree problem

引用

MEMETIC COMPUTING 2020年第3期12卷 185-217页

作者： Dinh, Thanh Pham Thanh, Binh Huynh Thi Ba, Trung Tran Binh, Long Nguyen Taybac Univ Fac Nat Sci & Technol Son La Vietnam Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

The Multifactorial Evolutionary Algorithm (MFEA) has emerged as an effective variant of the evolutionary algorithm. MFEA has been successfully applied to deal with various problems with many different types of solution encodings. Although clustered tree problems play an important role in real life, there haven't been much research on exploiting the strengths of MFEA to solve these problems. One of the challenges in applying the MFEA is to build specific evolutionary operators of the MFEA algorithm. To exploit the advantages of the Cayley codes in improving the MFEA's performance, this paper introduces MFEA with representation scheme based on the Cayley code to deal with the clustered tree problems. The new evolutionary operators in MFEA have two different levels. The purpose of the first level is to construct a spanning tree which connects to a vertex in each cluster, while the objective of the second one is to determine the spanning tree for each cluster. We focus on evaluating the efficiency of the new MFEA algorithm on known Cayley codes when solving clustered tree problems. In the aspect of the execution time and the quality of the solutions found, each encoding type of the Cayley codes is analyzed when performed on both single-task and multi-task to find the solutions of one or two different clustered tree problems respectively. In addition, we also evaluate the effect of those encodings on the convergence speed of the algorithms. Experimental results show the level of effectiveness for each encoding type and prove that the Dandelion code outperforms the remaining encoding mechanisms when solving clustered tree problems.

关键词： Multifactorial evolutionary algorithm Clustered tree problems Evolutionary algorithms Cayley code prufer code Dandelion code Blob code

来源：评论

学校读者我要写书评

暂无评论

Counting nilpotent endomorphisms

引用

FINITE FIELDS AND THEIR APPLICATIONS 2006年第1期12卷 151-154页

作者： Crabb, MC Univ Aberdeen Dept Math Sci Aberdeen AB24 3UE Scotland

A variant of Priffer's classical proof of Cayley's theorem on the enumeration of labelled trees counts the nilpotent self-maps of a pointed finite set. Essentially, the same argument can be used to establish the result of Fine and Herstein [Illinois J. Math. 2 (1958) 499-504] that the number of nilpotent n x n matrices over the finite field F-q is q(n)((n-1)). (c) 2005 Elsevier Inc. All rights reserved.

关键词： nilpotent matrix prufer code

来源：评论

学校读者我要写书评

暂无评论

A generalized enumeration of labeled trees and reverse prufer algorithm

引用

JOURNAL OF COMBINATORIAL THEORY SERIES A 2007年第7期114卷 1357-1361页

作者： Seo, Seunghyun Shin, Heesung Cheongju Univ Dept Math Educ Cheongju 360764 Chungbuk South Korea Korea Adv Inst Sci & Technol Dept Math Taejon 305701 South Korea

A leader of a tree T on [n] is a vertex which has no smaller descendants in T. Gessel and Seo showed that Sigma(T is an element of Tn) u(C)((# of leaders in T))((degree of 1 in T)) = uP(n-1)(1, u, cu), which is a generalization of Cayley's formula, where T-n is the set of trees on [n] and P-n(a, b, c) = c(n-1)Pi(i=1)(ia+(n-i)b+c). Using a variation of the prufer code which is called a RP-code, we give a simple bijective proof of Gessel and Seo's formula. (C) 2007 Elsevier Inc. All rights reserved.

关键词： tree prufer code leader bijection

来源：评论

学校读者我要写书评

暂无评论

Efficient prufer-Like Coding and Counting Labelled Hypertrees

引用

ALGORITHMICA 2009年第2期54卷 208-225页

作者： Shannigrahi, Saswata Pal, Sudebkumar Prasant Tata Inst Fundamental Res Sch Technol & Comp Sci Mumbai 400005 Maharashtra India Indian Inst Technol Dept Comp Sci & Engn Kharagpur 721302 W Bengal India Indian Inst Technol Ctr Theoret Studies Kharagpur 721302 W Bengal India

We consider labelled r-uniform hypertrees, 2 <= r <= n, where n is the number of vertices in the hypertree. Any two hyperedges in a hypertree share at most one vertex and each hyperedge in an r-uniform hypertree contains exactly r vertices. We show that r-uniform hypertrees can be encoded in linear time using as little as n - 2 integers in the range [1, n]. The decoding algorithm also runs in linear time. For general hypertrees, we require codes of length n + p - 2 where p is the number of vertices belonging to more than one hyperedge in the given hypertree. Based on our coding technique, we show that there are at most n((n-2))- f (n, r)/(r-1)((r-2))*(n-1/r-1) distinct labelled r-uniform hypertrees, where f (n, r) is a lower bound on the number of labelled trees with maximum (vertex) degree exceeding (r - 1)+ n-1/r-1 - 2. We suggest a counting scheme for determining such a lower bound f (n, r).

关键词： Hypertree prufer code Coding Counting r-uniform

来源：评论

学校读者我要写书评

暂无评论

An Effective Representation Scheme in Multifactorial Evolutionary Algorithm for Solving Cluster Shortest-Path Tree Problem

An Effective Representation Scheme in Multifactorial Evoluti...

引用

IEEE Congress on Evolutionary Computation (IEEE CEC) as part of the IEEE World Congress on Computational Intelligence (IEEE WCCI)

作者： Pham Dinh Thanh Dinh Anh Dung Tran Ngoc Tien Huynh Thi Thanh Binh Taybac Univ Fac Math Phys Informat Chieng Ngan Son La Vietnam Hanoi Univ Sci & Technol Sch Informat & Commun Technol Hanoi Vietnam

ISBN: (纸本)9781509060177

The wide range of applications of Cluster Tree Problems has been motivating extensive research into various algorithms and techniques with a view to promoting both efficiency of the solving and qualities of solutions. A representative of Cluster Tree Problems, the Cluster Shortest-Path Tree Problem (CSTP) arose from the practical need to optimize network systems such as irrigation systems, network cables and distribution systems. In this paper, we proposed the Multifactorial Evolutionary Algorithm (MFEA) to approach the CSTP with a representation scheme based on the Cayley code. The proposed algorithm exploit advantages of Cayley code for improving the MFEAs performance and quality solutions. This approach also applied new decoding method to transform the solution from the unified search space to the tasks. Experiments were conducted to compare the performances of the proposed to another approximation algorithm on various set of instances. The experimental results show that proposed algorithm surpass existing algorithm on almost test cases.

关键词： Multifactorial Evolutionary Algorithm Clustered Shortest-Path Tree Problem Evolutionary Algorithm Genetic Algorithm Cayley code prufer code

来源：评论

学校读者我要写书评

暂无评论

Efficient prufer-Like Coding and Counting Labelled Hypertrees

引用

17th International Symposium on Algorithms and Computation (ISAAC 2006)

ISBN: (纸本)3540496947

关键词： Hypertree prufer code Coding Counting r-uniform

来源：评论

学校读者我要写书评

暂无评论

引用

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS 2016年第2期8卷 1650031-1-1650031-13页

作者： Mansour, Toufik Shattuck, Mark Univ Haifa Dept Math IL-3498838 Haifa Israel Univ Tennessee Dept Math Knoxville TN 37996 USA

Let T-n denote the set of trees on n labeled vertices. In this paper, we consider the statistic on T-n which records the number of vertices of odd degree and count trees having a prescribed number of such vertices. In doing so, we make use of a well-known bijection between members of T-n and the set of n-ary words of length n-2. In fact, we are able to study a generalization mod r of the aforementioned statistic for all r >= 2. In the cases when r = 2 and r = 3, further enumerative results for both words and trees may be given.

关键词： prufer code trees k-ary words generating function

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：