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

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Davis, Timothy A. Texas A&M Univ Dept Comp Sci & Engn College Stn TX 77843 USA

ISBN: (纸本)9781538659892

SuiteSparse:graphBLAS is a full implementation of the graphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. graphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. To illustrate graphBLAS, two graph algorithms are constructed in graphBLAS and compared with efficient implementations without graphBLAS: triangle counting and constructing the k-truss of a graph.

关键词： graph algorithms sparse matrix computations

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL graph algorithms ON A FIXED-SIZE LINEAR-ARRAY

引用

IEEE TRANSACTIONS ON COMPUTERS 1987年第4期36卷 460-470页

作者： DOSHI, KA VARMAN, PJ Department of Electrical and Computer Engineering Rice University

Parallel algorithms for computing the minimum spanning tree of a weighted undirected graph, and the bridges and articulation points of an undirected graphs on a fixed-size linear array of processors are presented. For a graph of n vertices, the algorithms operate on a linear array of p processors and require O(n2/p) time for all p, 1 ≤ p ≤ n. In particular, using n processors the algorithms require O(n) time which is optimal on this model. The paper describes two approaches to limit the communication requirements for solving the problems. The first is a divide-and-conquer strategy applied to Sollin"s algorithm for finding the minimum spanning tree of a graph. The second uses a novel data-reduction technique that constructs an auxiliary graph with no more than 2n − 2 edges, whose bridges and articulation points are the bridges and articulation points of the original graph.

关键词： Array processors articulation points bridges graph algorithms minimum spanning tree parallel algorithms pipelining

来源：评论

学校读者我要写书评

暂无评论

graph algorithms And Applications 4

引用

2006年

作者： Giuseppe Liotta Roberto Tamassia Ioannis G Tollis

ISBN: (数字)9789812773296

ISBN: (纸本)9789812568441;9789812773296

This book contains Volume 7 of the Journal of graph algorithms and Applications (JGAA). JGAA is a peer-reviewed scientific journal devoted to the publication of high-quality research papers on the analysis, design, implementation, and applications of graph algorithms. Areas of interest include computational biology, computational geometry, computer graphics, computer-aided design, computer and interconnection networks, constraint systems, databases, graph drawing, graph embedding and layout, knowledge representation, multimedia, software engineering, telecommunications networks, user interfaces and visualization, and VLSI circuit *** algorithms and Applications 4 presents contributions from prominent authors and includes selected papers from (a) the Seventh International Workshop on algorithms and Data Structures (WADS 2001) and (b) the 2001 Symposium on graph Drawing (GD 2001). All papers in the book have extensive diagrams and offer a unique treatment of graph algorithms focusing on the important applications.

关键词： graph theory graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing optimal electronic and mathematical properties of Buckyball nanoparticle using graph algorithms

引用

COMPEL-THE INTERNATIONAL JOURNAL FOR COMPUTATION AND MATHEMATICS IN ELECTRICAL AND ELECTRONIC ENGINEERING 2012年第2期31卷 387-400页

作者： Khataee, H. R. Ibrahim, M. Y. Sourchi, S. Eskandari, L. Noranis, M. A. Teh Univ Putra Malaysia Dept Comp Sci Serdang Malaysia Monash Univ Sch Appl Sci & Engn Melbourne Vic 3004 Australia Univ Tabriz Dept Comp Sci Tabriz Iran

Purpose - One of the significant underlying principles of nanorobotic systems deals with the understanding and conceptualization of their respective complex nanocomponents. This paper introduces a new methodology to compute a set of optimal electronic and mathematical properties of Buckyball nanoparticle using graph algorithms based on dynamic programming and greedy algorithm. Design/methodology/approach - Buckyball, C-60, is composed of sixty equivalent carbon atoms arranged as a highly symmetric hollow spherical cage in the form of a soccer ball. At first, Wiener, hyper-Wiener, Harary and reciprocal Wiener indices were computed using dynamic programming and presented them as: W(Buckyball) = 11870.4, WW(Buckyball) = 52570.9, Ha(Buckyball) = 1022 and RW(Buckyball) = 346.9. The polynomials of Buckyball, Hosoya and hyper-Hosoya, which are in relationship with Buckyball's indices, have also been computed. The relationships between Buckyball's indices and polynomials were then computed and demonstrated a good agreement with their mathematical equations. Also, a graph algorithm based on greedy algorithms was used to find some optimal electronic aspects of Buckyball's structure by computing the Minimum Weight Spanning Tree (MWST) of Buckyball. Findings - The computed MWST was indicated that for connecting sixty carbon atoms of Buckyball together: the minimum numbers of double bonds were 30;the minimum numbers of single bonds were 29;and the minimum numbers of electrons were 178. These results also had good agreement with the principles of the authors' used greedy algorithm. Originality/value - This paper has used the graph algorithms for computing the optimal electronic and mathematical properties of BB. It has focused on mathematical properties of BB including Wiener, hyper-Wiener, Harary and reciprocal Wiener indices as well as Hosoya and Hyper-Hosoya polynomials and computerized them with dynamic programming graph algorithms.

关键词： Buckyball graph algorithms Dynamic programming Greedy algorithm Nanocomputational calculations

来源：评论

学校读者我要写书评

暂无评论

Optimizing graph algorithms for improved cache performance

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2004年第9期15卷 769-782页

作者： Park, JS Penner, M Prasanna, VK Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA Univ So Calif Dept Elect Engn Los Angeles CA 90089 USA

In this paper, we develop algorithmic optimizations to improve the cache performance of four fundamental graph algorithms. We present a cache-oblivious implementation of the Floyd-Warshall Algorithm for the fundamental graph problem of all-pairs shortest paths by relaxing some dependencies in the iterative version. We show that this implementation achieves the lower bound on processor-memory traffic of Omega(N-3/rootC), where N and C are the problem size and cache size, respectively. Experimental results show that this cache-oblivious implementation shows more than six times the improvement in real execution time over that of the iterative implementation with the usual row major data layout, on three state-of-the-art architectures. Second, we address Dijkstra's algorithm for the single-source shortest paths problem and Prim's algorithm for minimum spanning tree problem. For these algorithms, we demonstrate up to two times the improvement in real execution time by using a simple cache-friendly graph representation, namely adjacency arrays. Finally, we address the matching algorithm for bipartite graphs. We show performance improvements of two to three times in real execution time by using the technique of making the algorithm initially work on subproblems to generate a suboptimal solution and, then, solving the whole problem using the suboptimal solution as a starting point. Experimental results are shown for the Pentium III, UltraSPARC III, Alpha 21264, and MIPS R12000 machines.

关键词： cache-friendly algorithms cache-oblivious algorithms graph algorithms shortest path minimum spanning trees graph matching data layout optimizations algorithm performance

来源：评论

学校读者我要写书评

暂无评论

CGMgraph/CGMlib: Implementing and testing cgm graph algorithms on PC clusters and shared memory machines

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2005年第1期19卷 81-97页

作者： Chan, A Dehne, F Taylor, R Fayetteville State Univ Dept Math & Comp Sci Fayetteville NC 28301 USA Griffith Univ Sch ICT Brisbane Qld 4111 Australia Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on Coarse Grained Multicomputer (CGM) algorithms. CGMgraph implements parallel methods for various graph problems. Our implementations of deterministic list ranking, Euler tour, connected components, spanning forest, and bipartite graph detection are, to our knowledge, the first efficient implementations for PC clusters. Our library also includes CGMlib, a library of basic CGM tools such as sorting, prefix sum, one-to-all broadcast, all-to-one gather, h-Relation, all-to-all broadcast, array balancing, and CGM partitioning. Both libraries are available for download at http: //www. scs. carleton. ca/similar tocgm. In the experimental part of this paper, we demonstrate the performance of our methods on four different architectures: a gigabit connected high performance PC cluster, a smaller PC cluster connected via fast ethernet, a network of workstations, and a shared memory machine. Our experiments show that our library provides good parallel speedup and scalability on all four platforms. The communication overhead is, in most cases, small and does not grow significantly with an increasing number of processors. This is a very important feature of CGM algorithms which makes them very efficient in practice.

关键词： coarse-grained multiprocessor graph algorithms library parallel algorithms implementation processor cluster

来源：评论

学校读者我要写书评

暂无评论

Streaming data analytics via message passing with application to graph algorithms

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2014年第8期74卷 2687-2698页

作者： Plimpton, Steven J. Shead, Tim Sandia Natl Labs Albuquerque NM 87185 USA

The need to process streaming data, which arrives continuously at high-volume in real-time, arises in a variety of contexts including data produced by experiments, collections of environmental or network sensors, and running simulations. Streaming data can also be formulated as queries or transactions which operate on a large dynamic data store, e.g. a distributed database. We describe a lightweight, portable framework named PHISH which provides a communication model enabling a set of independent processes to compute on a stream of data in a distributed-memory parallel manner. Datums are routed between processes in patterns defined by the application. PHISH provides multiple communication backends including MPI and sockets/ZMQ. The former means streaming computations can be run on any parallel machine which supports MPI;the latter allows them to run on a heterogeneous, geographically dispersed network of machines. We illustrate how streaming MapReduce operations can be implemented using the PHISH communication model, and describe streaming versions of three algorithms for large, sparse graph analytics: triangle enumeration, sub-graph isomorphism matching, and connected component finding. We also provide benchmark timings comparing MPI and socket performance for several kernel operations useful in streaming algorithms. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Streaming data graph algorithms Message passing MPI Sockets Map Reduce

来源：评论

学校读者我要写书评

暂无评论

JGAP: a Java-based graph algorithms platform

引用

SOFTWARE-PRACTICE & EXPERIENCE 2001年第7期31卷 615-635页

作者： Chen, DY Chuang, TR Tsai, SC Natl Chi Nan Univ Dept Informat Management Nantou 545 Taiwan Acad Sinica Inst Informat Sci Taipei 115 Taiwan

We describe JGAP, a web-based platform for designing and implementing Java-coded graph algorithms. The platform contains a library of common data structures for implementing graph algorithms, features a 'plug-and-play' modular design for adding new algorithm modules, and includes a performance meter to measure the execution time of implemented algorithms. JGAP is also equipped with a graph editor to generate and modify graphs to have specific properties. JGAP's graphic user interface further allows users to compose, in a functional way, computation, sequences from existing algorithm modules so that output from an algorithm is used as input for another algorithm. Hence, JGAP can be viewed as a visual graph calculator for helping experiment with and teach graph algorithm design. Copyright (C) 2001 John Wiley & Sons, Ltd.

关键词： graph algorithms Java software visualization web-based software systems

来源：评论

学校读者我要写书评

暂无评论

Geometric Refactoring of Quantum and Reversible Circuits Using graph algorithms

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2024年第8期E107D卷 930-939页

作者： Lukac, Martin Nursultan, Saadat Krylov, Georgiy Keszocze, Oliver Rakhmettulayev, Abilmansur Kameyama, Michitaka Hiroshima City Univ Hiroshima 7313166 Japan Nazarbayev Univ Astana Kazakhstan Univ New Brunswick Fredericton NB Canada Friedrich Alexander Univ Erlangen Nurnberg FAU Nurnberg Germany Nazarbayev Intellectual Sch Astana Kazakhstan Tohoku Univ Sendai 9808577 Japan

With the advent of gated quantum computers and the regular structures for qubit layout, methods for placement, routing, noise estimation, and logic to hardware mapping become imminently required. In this paper, we propose a method for quantum circuit layout that is intended to solve such problems when mapping a quantum circuit to a gated quantum computer. The proposed methodology starts by building a Circuit Interaction graph (CIG) that represents the ideal hardware layout minimizing the distance and path length between the individual qubits. The CIG is also used to introduce a qubit noise model. Once constructed, the CIG is iteratively reduced to a given architecture (qubit coupling model) specifying the neighborhood, qubits, priority, and qubits noise. The introduced constraints allow us to additionally reduce the graph according to preferred weights of desired properties. We propose two different methods of reducing the CIG: iterative reduction or the iterative isomorphism search algorithm. The proposed method is verified and tested on a set of standard benchmarks with results showing improvement on certain functions while in average improving the cost of the implementation over the current state of the art methods.

关键词： quantum circuits qubuit layout graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Frameworks for designing in-place graph algorithms

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 123卷 1-19页

作者： Chakraborty, Sankardeep Mukherjee, Anish Raman, Venkatesh Satti, Srinivasa Rao Univ Tokyo Tokyo Japan Univ Warsaw Warsaw Poland HBNI Inst Math Sci Mumbai Maharashtra India Norwegian Univ Sci & Technol Trondheim Norway

Read-only memory (ROM) model is a classical model of computation to study time-space tradeoffs of algorithms. More recently, several graph algorithms have been studied under ROM model. In this paper, we study graph algorithms under two different relaxations of ROM model, referred to as the implicit and rotate models, and show that these simple relaxations allow us to implement fundamental graph search methods like BFS and DFS more space efficiently than in ROM model. All our algorithms are simple but quite subtle, and we believe that these models are practical enough to spur interest for other graph problems in these models. (C) 2021 The Author(s). Published by Elsevier Inc.

关键词： graph algorithms In-place algorithms Implicit model ROM model BFS DFS Topological sorting

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：