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,entitie...
详细信息
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.
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streamin...
详细信息
ISBN:
(纸本)9781728125848
Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.
We propose a new model for graph editing problems on intersection graphs called Geometricgraph Edit *** well-studied graph editing problems, adding and deleting vertices and edges are used as graph editing *** a graph...
详细信息
graph covers are a way to describe continuous maps (and homeomorphisms) of the Cantor set, more generally than e.g. Bratteli-Vershik systems. Every continuous map on a zero-dimensional compact set can be expressed by ...
详细信息
A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number c such that G is c-closed. Fox et al. [SIAM J. Comput.’20] defined c-closu...
详细信息
In this work we design graph neural network architectures that capture optimal approximation algorithms for a large class of combinatorial optimization problems, using powerful algorithmic tools from semidefinite prog...
详细信息
In this paper, we investigate quantum algorithms for graph colouring problems, in particular for 2- and 3-colouring of graphs. Our main goal is to establish a set of quantum representations and operations suitable for...
详细信息
In this paper, we investigate quantum algorithms for graph colouring problems, in particular for 2- and 3-colouring of graphs. Our main goal is to establish a set of quantum representations and operations suitable for the problem at hand. We propose unitaryas well as measurement-based quantum computations, also taking inspiration from answer set programming, a form of declarative programming close to traditional logic programming. The approach used is one in which we first generate arbitrary solutions to the problem, then constraining these according to the problem's input. Though we do not achieve fundamental speed-ups, our algorithms show how quantum concepts can be used for programming and moreover exhibit structural differences. For example, we compute all possible colourings at the same time. We compare our algorithms with classical ones, highlighting how the same type of difficulties give rise to NP-complete behaviour, and propose possible improvements. (C) 2008 Elsevier B.V. All rights reserved.
Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their correspon...
详细信息
Simultaneous representations of planar graphs and their duals normally require that the dual vertices to be placed inside their corresponding primal faces, and the edges of the dual graph to cross only their corresponding primal edges. Erten and Kobourov [C. Erten, S.G. Kobourov, Simultaneous embedding of a planar graph and its dual on the grid, Theory Computer Systems 38 (2005) 313-327] provided a linear time algorithm on simultaneous straight-line grid embedding of a 3-connected planar graph and its dual such that all the vertices are placed on grid points and each edge is drawn as one straight-line segment except for one which is drawn using two segments. Their drawing size is (2n - 2) x (2n - 2), where n is the total number of vertices in the graph and its dual. They raised an open question on whether there is a large class of planar graphs that allows this simultaneous straight-line grid embedding on a smaller grid. We answer this open question by giving a linear time simultaneous straight-line grid embedding algorithm for a 3-connected planar graph and its dual on a grid of size (n - 1) x n. (c) 2006 Elsevier B.V. All rights reserved.
A path cover of a graph G = (V, E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find...
详细信息
A path cover of a graph G = (V, E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in 0(1 V 19) time, to solve the path cover problem on distance-hereditary graphs. (C) 2007 Elsevier B.V. All rights reserved.
Image retrieval from an image database by the image objects and their spatial relationships has emerged as an important research subject in these decades. To retrieve images similar to a given query image, retrieval m...
详细信息
Image retrieval from an image database by the image objects and their spatial relationships has emerged as an important research subject in these decades. To retrieve images similar to a given query image, retrieval methods must assess the similarity degree between a database image and the query image by the extracted features with acceptable efficiency and effectiveness. This paper proposes a graph-based model SRG (spatial relation graph) to represent the semantic information of the contained objects and their spatial relationships in an image with no file annotation. In an SRG graph, the image objects are symbolized by the predefined class names as vertices and the spatial relations between object pairs are represented as arcs. The proposed model assesses the similarity degree between two images by calculating the maximum common subgraph of two corresponding SRG's through intersection, which has quadratic time complexity owing to the characteristics of SRG. Its efficiency remains quadratic regardless of the duplication rate of the object symbols. The extended model SRG(T) is also proposed, with the same time complexity, for the applications that need to consider the topological relations among objects. A synthetic symbolic image database and an existing image dataset are used in the conducted experiments to verify the performance of the proposed models. The experimental results show that the proposed models have compatible retrieval quality with remarkable efficiency improvements compared with three well-known methods LCS_Clique, SIMR, and 2D Be-string, where LCS_Clique utilizes the number of objects in the maximum common sub-image as its similarity function, SIMR uses accumulation-based similarity function of similar object pairs, and 2D Be-string calculates the similarity of 2D patterns by the linear combination of two 1D similarities. (C) 2007 Elsevier B.V. All rights reserved.
暂无评论