检索结果-南通市图书馆

A survey on dynamic graph processing on GPUs: concepts, terminologies and systems

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Frontiers of Computer Science 2024年第4期18卷 1-23页

作者： Hongru GAO Xiaofei LIAO Zhiyuan SHAO Kexin LI Jiajie CHEN Hai JIN National Engineering Research Center for Big Data Technology and System/Services Computing Technology and System Lab/Cluster and Grid Computing Lab School of Computer Science and TechnologyHuazhong University of Science and TechnologyWuhan 430074China Zhejiang Lab Hangzhou 311121China

graphs that are used to model real-world entities with vertices and relationships among entities with edges,have proven to be a powerful tool for describing real-world problems in *** most real-world scenarios,entities and their relationships are subject to constant *** that record such changes are called dynamic *** recent years,the widespread application scenarios of dynamic graphs have stimulated extensive research on dynamic graph processing systems that continuously ingest graph updates and produce up-to-date graph analytics *** the scale of dynamic graphs becomes larger,higher performance requirements are demanded to dynamic graph processing *** the massive parallel processing power and high memory bandwidth,GPUs become mainstream vehicles to accelerate dynamic graph processing ***-based dynamic graph processing systems mainly address two challenges:maintaining the graph data when updates occur(i.e.,graph updating)and producing analytics results in time(i.e.,graph computing).In this paper,we survey GPU-based dynamic graph processing systems and review their methods on addressing both graph updating and graph *** comprehensively discuss existing dynamic graph processing systems on GPUs,we first introduce the terminologies of dynamic graph processing and then develop a taxonomy to describe the methods employed for graph updating and graph *** addition,we discuss the challenges and future research directions of dynamic graph processing on GPUs.

关键词： dynamic graphs graph processing graph algorithms GPUs

Grid graph-based large-scale point clouds registration

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

International Journal of Digital Earth 2023年第1期16卷 2448-2466页

作者： Yi Han Guangyun Zhang Rongting Zhang School of Geomatics Science and Technology Nanjing Tech UniversityNanjingPeople's Republic of China

Automatic registration of unordered point clouds is the prerequisite forurban reconstruction. However, most of the existing technologies stillsuffer from some limitations. On one hand, most of them are sensitive tonoise and repetitive structures, which makes them infeasible for theregistration of large-scale point clouds. On the other hand, most of themdealing with point clouds with limited overlaps and unpredictablelocation. All these problems make it difficult for registration technology toobtain qualified results in outdoor point cloud. To overcome theselimitations, this paper presents a grid graph-based point cloud registration(GGR) algorithm to align pairwise scans. First, point cloud is divided into aset of 3D grids. We propose a voting strategy to measure the similaritybetween two grids based on feature descriptor, transforming thesuperficial correspondence into 3D grid expression. Next, a graphmatching is proposed to capture the spatial consistency from putativecorrespondences, and graph matching hierarchically refines thecorresponding grids until obtaining point-to-point *** experiments demonstrated that the proposed algorithmobtains good performance in terms of successful registration rate, rotationerror, translation error, and outperformed the state-of-the-art approaches.

关键词： Point cloud alignment scan matching graph algorithms reconstruction

Improved kernels for triangle packing in tournaments

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

Science China(Information Sciences) 2023年第5期66卷 100-113页

作者： Hanchun YUAN Qilong FENG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Lab on Bioinformatics Central South University

Triangle packing problem has been paid lots of attention to in the literature. In this paper, we study the kernelization of the triangle packing problem in tournaments. For the parameterized arc-disjoint triangle packing problem in tournaments, we find a maximal arc-disjoint triangle packing with the number of vertices bounded by 2.5k. Based on the relation between the maximal arc-disjoint triangle packing and the vertices outside of the packing, a kernel of size 3.5k for the problem is obtained, improving the previous best one 6k. For the parameterized vertex-disjoint triangle packing problem in sparse tournaments, several new properties between the triangles in maximal vertex-disjoint triangle packing and the arcs in the feedback arc set are presented, which result in a kernel of size 7k for the problem, improving the previous best one of *** also give a 7k vertex kernel for the parameterized feedback vertex set problem in sparse *** kernelization process presented in this paper for the parameterized arc-disjoint triangle packing can be applied to solve the parameterized arc-disjoint triangle packing problem on other restricted directed graph classes.

关键词： tournaments triangle packing kernelization fixed-parameter tractable graph algorithms

Formal Derivation of graph AlgorithmicPrograms Using Partition-and-Recur

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

Journal of Computer Science & Technology 1998年第6期13卷 553-561页

作者：薛锦云 Computer Software Institute Jiangxi Normal University Nanchang P. R. China

In this paper, we derive, by presenting some suitable notations, three typical graph algorithms and corresponding programs using a unified approach, partition-and-recur. We putemphasis on the derivation rather than the algorithms themselves. The main ideas and lugesnutty of these algorithms are revealed by formula deduction. Success in these examples givesus more evidence that partition-and-recur is a simple and practical approach and developingenough suitable notations is the key in designing and deriving efficient and correct algorithmicprograms.

关键词： graph algorithms method of algorithm design program derivation formalmethod.

维普期刊数据库

A PARALLEL ALGORITHM FOR GENERATINGMULTIPLE ORDERING SPANNING TREESIN UNDIRECTED WEIGHTED graphS

在线全文

学校读者我要写书评

暂无评论

Acta Mathematicae Applicatae Sinica 1999年第3期15卷 303-309页

作者：马军马绍汉岩间一雄顾谦平 Department of Computer Science Shandong University Jinan China Dept. of Comput. Sci. & Comm. Eng. Kyushu University Fukuoka City Japan Dept. of Software Univ. of Aizu Tsuruga Aizu Wakamatsu City Fukushima Japan

In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).

关键词： Parallel algorithms minimum spanning trees networks graph algorithms

维普期刊数据库

A Note on the Matching Polynomials of Paths and Cycles

在线全文

学校读者我要写书评

暂无评论

Chinese Quarterly Journal of Mathematics 2018年第2期33卷 140-143页

作者： ZHANG Hai-liang Department of Mathematics Taizhou University Linhai 317000 Zhejiang China

The spectra of matching polynomials which are useful in the computations of resonance energy and grand canonical partition functions of molecular's. It also present other properties for certain classes of graphs and lattices. In [1] Balasubramanian calculates several matching polynomials and matching roots of several molecular graphs. He found that the matching polynomial of C_6, C_(10), C_(14), C_(18) and C_(22) are divided by x^2-2. In this note,we prove that x^2-2 divides MC_(4k+2)(x), k = 1, 2,..., n and obtain some other properties of matching polynomials of paths and cycles.

关键词： graph algorithms Matching polynomial Matching roots Combinatorial problems

维普期刊数据库