A Sharding Scheme Based on Graph Partitioning Algorithm for Public Blockchain

Blockchain technology,with its attributes of decentralization,immutability,and traceability,has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes.However,transaction performance and scalability has become the main challenges hindering the widespread adoption of blockchain.Due to its inability to meet the demands of high-frequency trading,blockchain cannot be adopted in many scenarios.To improve the transaction capacity,researchers have proposed some on-chain scaling technologies,including lightning networks,directed acyclic graph technology,state channels,and shardingmechanisms,inwhich sharding emerges as a potential scaling technology.Nevertheless,excessive cross-shard transactions and uneven shard workloads prevent the sharding mechanism from achieving the expected aim.This paper proposes a graphbased sharding scheme for public blockchain to efficiently balance the transaction distribution.Bymitigating crossshard transactions and evening-out workloads among shards,the scheme reduces transaction confirmation latency and enhances the transaction capacity of the blockchain.Therefore,the scheme can achieve a high-frequency transaction as well as a better blockchain scalability.Experiments results show that the scheme effectively reduces the cross-shard transaction ratio to a range of 35%-56%and significantly decreases the transaction confirmation latency to 6 s in a blockchain with no more than 25 shards.

Computing All Pairs Shortest Paths on Sparse Graphs with Articulation Points

In most network analysis tools the computation of the shortest paths between all pairs of nodes is a fundamental step to the discovery of other properties. Among other properties is the computation of closeness centrality, a measure of the nodes that shows how central a vertex is on a given network. In this paper, the authors present a method to compute the All Pairs Shortest Paths on graphs that present two characteristics： abundance of nodes with degree value one, and existence of articulation points along the graph. These characteristics are present in many real life networks especially in networks that show a power law degree distribution as is the case of biological networks. The authors＇ method compacts the single nodes to their source, and then by using the network articulation points it disconnects the network and computes the shortest paths in the biconnected components. At the final step the authors proposed methods merges the results to provide the whole network shortest paths. The authors＇ method achieves remarkable speedup compared to state of the art methods to compute the shortest paths, as much as 7 fold speed up in artificial graphs and 3.25 fold speed up in real application graphs. The authors＇ performance improvement is unlike previous research as it does not involve elaborated setups since the authors algorithm can process significant instances on a popular workstation.

User-Oriented Graph Based Frequency Allocation Algorithm for Densely Deployed Femtocell Network

Femtocell is a promising technology for improving indoor coverage and offloading the macrocell.Femtocells tend to be densely deployed in populated areas such as the dormitories.However,the inter-tier interference seriously exists in the co-channel Densely Deployed Femtocell Network(DDFN).Since the Femtocell Access Points(FAPs) are randomly deployed by their customers,the interference cannot be predicted in advance.Meanwhile,new characteristics such as the short radius of femtocell and the small number of users lead to the inefficiency of the traditional frequency reuse algorithms such as Fractional Frequency Reuse(FFR).Aiming for the downlink interference coordination in the DDFN,in this paper,we propose a User-oriented Graph based Frequency Allocation(UGFA)algorithm.Firstly,we construct the interference graph for users in the network.Secondly,we study the conventional graph based resources allocation algorithm.Then an improved two steps graph based frequency allocation mechanism is proposed.Simulation results show that UGFA has a high frequency reuse ratio mean while guarantees a better throughput.

Near-Optimal Placement of Secrets in Graphs

We consider the reconstruction of shared secrets in communication networks, which are modelled by graphs whose components are subject to possible failure. The reconstruction probability can be approximated using minimal cuts, if the failure probabilities of vertices and edges are close to zero. As the main contribution of this paper, node separators are used to design a heuristic for the near-optimal placement of secrets sets on the vertices of the graph.

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

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 applications.In most real-world scenarios,entities and their relationships are subject to constant changes.Graphs that record such changes are called dynamic graphs.In 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 results.As the scale of dynamic graphs becomes larger,higher performance requirements are demanded to dynamic graph processing systems.With the massive parallel processing power and high memory bandwidth,GPUs become mainstream vehicles to accelerate dynamic graph processing tasks.GPU-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 computing.To 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 computing.In addition,we discuss the challenges and future research directions of dynamic graph processing on GPUs.

Multiple Object Tracking through Background Learning

This paper discusses about the new approach of multiple object track-ing relative to background information.The concept of multiple object tracking through background learning is based upon the theory of relativity,that involves a frame of reference in spatial domain to localize and/or track any object.Thefield of multiple object tracking has seen a lot of research,but researchers have considered the background as redundant.However,in object tracking,the back-ground plays a vital role and leads to definite improvement in the overall process of tracking.In the present work an algorithm is proposed for the multiple object tracking through background learning.The learning framework is based on graph embedding approach for localizing multiple objects.The graph utilizes the inher-ent capabilities of depth modelling that assist in prior to track occlusion avoidance among multiple objects.The proposed algorithm has been compared with the recent work available in literature on numerous performance evaluation measures.It is observed that our proposed algorithm gives better performance.

Efficient Parallel Algorithms for Some Graph Theory Problems

In this paper,a sequential algorithm computing the all vertex pair distance matrix D and the path matrix Pis given.On a PRAM EREW model with p,1≤p≤n^2,processors,a parallel version of the sequential algorithm is shown.This method can also be used to get a parallel algorithm to compute transitive closure arrayof an undirected graph.The time complexify of the parallel algorithm is O(n^3/p).If D,P andare known,it is shown that the problems to find all connected components, to compute the diameter of an undirected graph,to determine the center of a directed graph and to search for a directed cycle with the minimum(maximum)length in a directed graph can all be solved in O(n^2/p^+ logp)time.

A Note on the Matching Polynomials of Paths and Cycles

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.

Grid graph-based large-scale point clouds registration

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 correspondences.Comprehensive 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.

Necessary and Sufficient Conditions for Consensus in Third Order Multi-Agent Systems

We deal with a consensus control problem for a group of third order agents which are networked by digraphs.Assuming that the control input of each agent is constructed based on weighted difference between its states and those of its neighbor agents, we aim to propose an algorithm on computing the weighting coefficients in the control input. The problem is reduced to designing Hurwitz polynomials with real or complex coefficients. We show that by using Hurwitz polynomials with complex coefficients, a necessary and sufficient condition can be obtained for designing the consensus algorithm. Since the condition is both necessary and sufficient, we provide a kind of parametrization for all the weighting coefficients achieving consensus. Moreover, the condition is a natural extension to second order consensus, and is reasonable and practical due to its comparatively decreased computation burden. The result is also extended to the case where communication delay exists in the control input.

QIM digital watermarkingbased on LDPC code and messagepassingunder scalingattacks

Watermarking system based on quantization index modulation （QIM） is increasingly popular in high payload applications,but it is inherently fragile against amplitude scaling attacks.In order to resist desynchronization attacks of QIM digital watermarking,a low density parity check （LDPC） code-aided QIM watermarking algorithm is proposed,and the performance of QIM watermarking system can be improved by incorporating LDPC code with message passing estimation/detection framework.Using the theory of iterative estimation and decoding,the watermark signal is decoded by the proposed algorithm through iterative estimation of amplitude scaling parameters and decoding of watermark.The performance of the proposed algorithm is closer to the dirty paper Shannon limit than that of repetition code aided algorithm when the algorithm is attacked by the additive white Gaussian noise.For constant amplitude scaling attacks,the proposed algorithm can obtain the accurate estimation of amplitude scaling parameters.The simulation result shows that the algorithm can obtain similar performance compared to the algorithm without desynchronization.

Dynamic airspace sectorization via improved genetic algorithm

This paper deals with dynamic airspace sectorization （DAS） problem by an improved genetic algorithm （iGA）. A graph model is first constructed that represents the airspace static structure. Then the DAS problem is formulated as a graph-partitioning problem to balance the sector workload under the premise of ensuring safety. In the iGA, multiple populations and hybrid coding are applied to determine the optimal sector number and airspace sectorization. The sector constraints are well satisfied by the improved genetic operators and protect zones. This method is validated by being applied to the airspace of North China in terms of three indexes, which are sector balancing index, coordination workload index and sector average flight time index. The improvement is obvious, as the sector balancing index is reduced by 16.5 %, the coordination workload index is reduced by 11.2 %, and the sector average flight time index is increased by 11.4 % during the peak-hour traffic.

CREATION OF OPTIMAL MOVEMENT STRATEGY OF PLURAL MOVING OB-JECTS BY GA

The topographic information of a closed world is expressed as a graph. The plural mov- ingobjects which go and back in it according to a single moving strategy are supposed.The moving strategy is expressed by numerical values as a decision table. Coding is performed with this table as chromosomes, and this is optimized by using genetic algorithm. These environments were realized on a computer, and the simulation was carried out. As the result, the learning of the method to act so that moving objects do not obstruct mutually was recognized, and it was confirmed that these methods are effective for optimizing moving strategy.

An Overview of Kernelization Algorithms for Graph Modification Problems

Kernelization algorithms for graph modification problems are important ingredients in parameterized computation theory. In this paper, we survey the kernelization algorithms for four types of graph modification problems, which include vertex deletion problems, edge editing problems, edge deletion problems, and edge completion problems. For each type of problem, we outline typical examples together with recent results, analyze the main techniques, and provide some suggestions for future research in this field.

Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.

Formal Derivation of Graph AlgorithmicPrograms Using Partition-and-Recur

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.

A PARALLEL ALGORITHM FOR GENERATINGMULTIPLE ORDERING SPANNING TREESIN UNDIRECTED WEIGHTED GRAPHS

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).

Task Graph Reduction Algorithm for Hardware/Software Partitioning

Hardware/software（HW/SW） partitioning is one of the key processes in an embedded system.It is used to determine which system components are assigned to hardware and which are processed by software.In contrast with previous research that focuses on developing efficient heuristic,we focus on the pre-process of the task graph before the HW/SW partitioning in this paper,that is,enumerating all the sub-graphs that meet the requirements.Experimental results showed that the original graph can be reduced to 67% in the worst-case scenario and 58% in the best-case scenario.In conclusion,the reduced task graph saved hardware area while improving partitioning speed and accuracy.

Approximation Algorithms for Steiner Connected Dominating Set

Steiner connected dominating set （SCDS） is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP- hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of （2 ＋ 1/（m - 1））H（min（△, k）） ＋O（1）, which outperforms the previous best result （c ＋ 1）H（min（△, k）） ＋ O（1） in the case of m ≥ 1 ＋1/（c - 1）, where c is the best approximation ratio for Steiner tree, A is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0 ≤ m ≤ min（△, k） and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2 ln（min（△, k）） ＋ O（1）, which can also be improved to 2 lnk if the optimal solution is greater than c·e^2c＋1/2（c＋1）.

Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.