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

Constructing Node-Independent Spanning Trees in Augmented Cubes

FUNDAMENTA INFORMATICAE 2020年第2期176卷 103-128页

作者： Cheng, Baolei Fan, Jianxi Lyu, Qiang Lin, Cheng-Kuan Li, Xiaoyan Chen, Guo Soochow Univ Sch Comp Sci & Technol Suzhou 215006 Peoples R China Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China

For a network, edge/node-independent spanning trees (ISTs) can not only tolerate faulty edges/nodes, but also be used to distribute secure messages. As important node-symmetric variants of the hypercubes, the augmented cubes have received much attention from researchers. The n-dimensional augmented cube AQ(n) is both (2n - 1)-edge-connected and (2n - 1)-nodeconnected (n not equal 3), thus the well-known edge conjecture and node conjecture of ISTs are both interesting questions in AQ(n). So far, the edge conjecture on augmented cubes was proved to be true. However, the node conjecture on AQ(n) is still open. In this paper, we further study the construction principle of the node-ISTs by using the double neighbors of every node in the higher dimension. We prove the existence of 2k - 1 node-ISTs rooted at node 0 in AQ(n)(vertical bar 00...0}/n-k (n >= k >= 4) by proposing an ingenious way of construction and propose a corresponding O(N logN) time algorithm, where N = 2(k) is the number of nodes in AQ(n)(vertical bar 00...0}/n-k.

关键词： Augmented cubes node-independent spanning trees constructive algorithm secure message distribution

来源：评论

学校读者我要写书评

暂无评论

Single Layer Feedforward Networks Construction Based on Orthogonal Least Square and Particle Swarm Optimization 15th

Single Layer Feedforward Networks Construction Based on Orth...

引用

15th International Conference on Artificial Intelligence and Soft Computing (ICAISC)

作者： Wu, Xing Rozycki, Pawel Wilamowski, Bogdan M. Auburn Univ Auburn AL 36849 USA Univ Informat Technol & Management Rzeszow Sucharskiego 2 PL-35225 Rzeszow Poland

ISBN: (纸本)9783319393780;9783319393773

According to the simplicity and universal approximation capability, single layer feedforward networks (SLFN) are widely used in classification and regression problems. The paper presents a new OLS-PSO constructive algorithm based on Orthogonal Least Square (OLS) method and Particle Swarm Optimization (PSO) algorithm. Instead of evaluating the orthogonal components of each neuron as the conventional OLS method, a new recursive formulation is derived. Then based on the new evaluation of each neuron's contribution, the PSO algorithm is used to seek the optimal parameters of the new neuron in continuous space. The proposed algorithm is experimented on some practical regression problems and compared with other constructive algorithms. Results show that proposed OLS-PSO algorithm could achieve a compact SLFN with good generalization ability.

关键词： Single Layer Feedforward Networks (SLFN) constructive algorithm Orthogonal Least Square (OLS) Particle Swarm Optimization (PSO)

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for the Lovasz Local Lemma and Graph Coloring 14

Distributed Algorithms for the Lovasz Local Lemma and Graph ...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Chung, Kai-Min Pettie, Seth Su, Hsin-Hao Acad Sinica Taipei Taiwan Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9781450329446

The Lovasz Local Lemma (LLL), introduced by Erd}os and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n \bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires O (log2 n) rounds of communication in a distributed network. In this paper we provide two new distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm. For clarity we express our results in terms of the symmetric LLL though both algorithms deal with the asymmetric version as well. Let p bound the probability of any bad event and d be the maximum degree in the dependency graph of the bad events. When epd2 < 1 we give a truly simple LLL algorithm running in O(log 1=epd2 n) rounds. Under the tighter condition ep(d + 1) < 1, we give a slightly slower algorithm running in O(log2 d . log 1=ep(d+1) n) rounds. Furthermore, we give an algorithm that runs in sublogarithmic rounds under the condition p . f (d) < 1, where f (d) is an exponential function of d. Although the conditions of the LLL are locally verifiable, we prove that any distributed LLL algorithm requires Omega(log* n) rounds. In many graph coloring problems the existence of a valid coloring is established by one or more applications of the LLL. Using our LLL algorithms, we give logarithmic-time distributed algorithms for frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring.

关键词： Lovasz Local Lemma distributed graph coloring constructive algorithm probabilistic method locality

来源：评论

学校读者我要写书评

暂无评论

The boundary of the Milnor fiber of the singularity f (x, y) plus zg(x, y)=0

引用

EUROPEAN JOURNAL OF MATHEMATICS 2020年第4期6卷 1191-1215页

作者： Sigurdsson, Baldur Univ Nacl Autonoma Mexico Inst Matemat Cuernavaca 62210 Morelos Mexico

Let f, g is an element of C{x, y} be germs of functions defining plane curve singularities without common components in (C-2, 0) and let Phi(x, y, z) = f (x, y) + zg(x, y). We give an explicit algorithm producing a plumbing graph for the boundary of the Milnor fiber of Phi in terms of a common resolution for f and g. We give an example of a choice for f and g yielding a boundary of a Milnor fiber having more than one irreducible component.

关键词： Milnor fiber boundary Plumbed manifold constructive algorithm

来源：评论

学校读者我要写书评

暂无评论

Degree-constrained ALM tree construction algorithm for heterogeneous access environment

Degree-constrained ALM tree construction algorithm for heter...

引用

IEEE Pacific Rim Conference on Communications, Computers and Signal Processing

作者： Takahashi, E. Osuga, T. Taniguchi, K. Wakamiya, N. Service Platforms Research Laboratories NEC Corporation Japan Graduate School of Information Science and Technology Osaka University Japan

ISBN: (纸本)9781424411894

Point-to-multipoint bulk data transfer using application-layer multicast (ALM) is discussed. In ALM, each host participating in an application session makes copies of received data by application-layer manipulation and forwards the copies to other hosts via unicast connections. Therefore, the performance, especially for access link speed, of hosts strongly affects overall delivery performance. In heterogeneous access environments, there is a strong possibility that some hosts with low-speed links decrease overall delivery performance. However, many previous solutions constructed ALM trees by introducing arbitrary degree allocations and by not well considering a diversity of access link speeds of hosts. This paper proposes an algorithm to construct an efficient ALM tree from hosts with heterogeneous access lines. This algorithm minimizes delivery completion time and lets many hosts complete reception of all data as fast as possible. The effectiveness of the algorithm is verified using simulations.

关键词： hosts Access algorithms application layer constructive algorithm Heterogeneous reception

来源：评论

学校读者我要写书评

暂无评论

Fuzzy Identification of Dynamic Systems with Adaptive Structure

Fuzzy Identification of Dynamic Systems with Adaptive Struct...

引用

5th International Multi-Conference on Systems, Signals and Devices

作者： Alimi, Sonia Chtourou, Mohamed Natl Sch Engn Sfax Res Unit Intelligent Control Design & Optimizat C Dept Elect Engn Sfax Tunisia

ISBN: (纸本)9781424422050

This paper deals with two approaches for on line structure identification of fuzzy models. In the first one, a constructive algorithm is adopted to generate the fuzzy rules: it starts with a single pattern and a single fuzzy rule and grows progressively to reduce the system error within the specified tolerance. In the second one, an evolutionary algorithm is applied based on an alternation between incremental and pruning criteria. Indeed, the rule base is expanded when the model can not reduce the system error and one rule is removed if it has a petty contribution in the model output along some patterns. The presented approaches have been applied for two examples of dynamic systems to compare the identification performance.

关键词： Structure identification constructive algorithm Evolutionary algorithm Fuzzy Inference System

来源：评论

学校读者我要写书评

暂无评论

Implementing Graph Coloring Heuristic in Construction Phase of Curriculum-Based Course Timetabling Problem

Implementing Graph Coloring Heuristic in Construction Phase ...

引用

IEEE Symposium on Computers and Informatics (ISCI)

作者： Azlan, Ammar Hussin, Naimah Mohd Univ Teknol MARA Perlis Dept Comp Sci Fac Comp & Math Sci Kangar Malaysia

ISBN: (纸本)9781479902101

Curriculum-based course timetabling problem (CB-CTP) is a classical problem that is still being researched on nowadays. There are two phases in solving CB-CTP. The first phase is the construction phase where a population of initial solutions is generated. The second phase is the optimization phase where the final optimal solution is produced. While most papers concentrate on the optimization phase, this paper focuses on the construction phase due to the importance of initial solutions to the optimization phase. The initial solutions are generated by implementing graph coloring heuristic to the CB-CTP. The graph coloring heuristics used in this paper are largest degree and largest weighted degree. Result from computational experiment shows that both methods are able to produce population of initial solutions for almost every data instance.

关键词： constructive algorithm curriculum-based course timetabling graph coloring heuristic initial solution

来源：评论

学校读者我要写书评

暂无评论

Memory-Optimised Parallel Processing of Hi-C Data 23

Memory-Optimised Parallel Processing of Hi-C Data

引用

23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP)

作者： Drocco, Maurizio Misale, Claudia Pezzi, Guilherme Peretti Tordini, Fabio Aldinucci, Marco Univ Turin Dept Comp Sci I-10124 Turin Italy

ISBN: (纸本)9781479984909

This paper presents the optimisation efforts on the creation of a graph-based mapping representation of gene adjacency. The method is based on the Hi-C process, starting from Next Generation Sequencing data, and it analyses a huge amount of static data in order to produce maps for one or more genes. Straightforward parallelisation of this scheme does not yield acceptable performance on multicore architectures since the scalability is rather limited due to the memory bound nature of the problem. This work focuses on the memory optimisations that can be applied to the graph construction algorithm and its (complex) data structures to derive a cache-oblivious algorithm and eventually to improve the memory bandwidth utilisation. We used as running example NuChart-II, a tool for annotation and statistic analysis of Hi-C data that creates a gene-centric neighborhood graph. The proposed approach, which is exemplified for Hi-C, addresses several common issue in the parallelisation of memory bound algorithms for multicore. Results show that the proposed approach is able to increase the parallel speedup from 7x to 22x (on a 32-core platform). Finally, the proposed C++ implementation outperforms the first R NuChart prototype, by which it was not possible to complete the graph generation because of strong memory-saturation problems.

关键词： Memory Memory PARALLEL PROCESSING (COMPUTERS) Multi-core processors Line graph ANNOTATIONS Scalability constructive algorithm memory bandwidth maps

来源：评论

学校读者我要写书评

暂无评论

Cheapest Insertion and Disruption of Routes Operators for Solving Multi-Depot Electric Vehicle Location Routing Problem with Time Windows and Battery Swapping via GRASP and RVND

Cheapest Insertion and Disruption of Routes Operators for So...

引用

IEEE Congress on Evolutionary Computation (IEEE CEC)

作者： Portela, Braulio M. O. Bernardino, Heder S. Goncalves, Luciana B. Soares, Stenio S. R. F. Univ Fed Juiz de Fora Juiz De Fora Brazil

ISBN: (纸本)9781728183923

The Multi-Depot Electric Vehicle Location Routing Problem with Time Windows and Battery Swapping (MDEVLRPTW-BS) aims to mitigate the environmental impacts caused by the use of vehicles with an internal combustion engine and uses economically viable electric vehicles in transportation services with time window restrictions. This problem is complex as one must define (i) the location of the battery swapping stations, (ii) the depots to be used from a list of candidates, and (iii) the assignment and routing of a fleet of electric vehicles. We propose here two constructive methods to solve MDEVLRPTW-BS, namely, Cheapest Insertion and Disruption of Routes. These constructive approaches are used with the Greedy Randomized Adaptive Search Procedure (GRASP) and the Random Variable Neighborhood Descent (RVND) method with six movement operators. Two of these operators, namely Isolate and ChangeBSS, are also proposed here for solving MDEVLRPTW-BS. The proposals are compared with a technique from the literature using instances with 5, 10, and 15 customers, and the proposed approaches presented good results, mainly regarding the processing time. Also, we propose new sets of instances larger than those from the literature. Thus, the search techniques can be analyzed when subjected to greater and more realistic situations. These new instances are composed of 100, 144, 288, 360, 420, and 600 customers. For these cases, the approaches also obtained good and promising results, mainly when the Disruption of Routes approach (GRASP-DR-RVND) is used.

关键词： electric vehicle constructive algorithm location routing problem battery swapping green logistic GRASP-RVND

来源：评论

学校读者我要写书评

暂无评论

Automatic synthesis of multiple place resource models with Petri nets

Automatic synthesis of multiple place resource models with P...

引用

American Control Conference

作者： Ferrarini, L Piroddi, L Politecn Milan Dipartimento Elettr & Informat I-20133 Milan Italy

ISBN: (纸本)0780383354

The paper focuses on the correct representation of shared resources in Petri net models of automated manufacturing systems, in the presence of concurrent independent operations, such as assembly and disassembly ones. In particular, an original multiple-place model is specifically derived and a constructive algorithm is proposed for the automatic synthesis of the resource model. The algorithm computes the number of resource places for each resource, as well as their connections to the recipes' transitions. Proper necessary conditions of "well-definiteness" are introduced for the partial models that are incrementally defined by the user.

关键词： manufacturing systems resource allocation Petri nets automatic synthesis multiple place resource models Petri net model resource sharing automated manufacturing systems constructive algorithm necessary condition

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：