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 centra...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.展开更多
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 p...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.展开更多
As a fundamental and effective tool for document understanding and organization, multi-document summarization enables better information services by creating concise and informative reports for large collections of do...As a fundamental and effective tool for document understanding and organization, multi-document summarization enables better information services by creating concise and informative reports for large collections of documents. In this paper, we propose a sentence-word two layer graph algorithm combining with keyword density to generate the multi-document summarization, known as Graph ＆ Keywordp. The traditional graph methods of multi-document summarization only consider the influence of sentence and word in all documents rather than individual documents. Therefore, we construct multiple word graph and extract right keywords in each document to modify the sentence graph and to improve the significance and richness of the summary. Meanwhile, because of the differences in the words importance in documents, we propose to use keyword density for the summaries to provide rich content while using a small number of words. The experiment results show that the Graph ＆ Keywordp method outperforms the state of the art systems when tested on the Duc2004 data set. Key words： multi-document, graph algorithm, keyword density, Graph ＆ Keywordp, Due2004展开更多
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 seri...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.展开更多
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,tra...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.展开更多
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 minim...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.展开更多
1 Introduction Estimating the number of triangles in a graph is a fundamental problem and has found applications in many fields.For example,in social network,it can help us understand how closely the local community s...1 Introduction Estimating the number of triangles in a graph is a fundamental problem and has found applications in many fields.For example,in social network,it can help us understand how closely the local community structure and nodes in the network are in close proximity.In this paper,we address this problem in the framework of graph streaming algorithms,which has received significant attention due to the increasing need to analyze large-scale graph data efficiently[1–3].However,most of these algorithms are not robust or are limited to unweighted graphs.展开更多
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 sho...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.展开更多
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 a...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.展开更多
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 a...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.展开更多
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,th...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.展开更多
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 desynchronizati...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.展开更多
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 ...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.展开更多
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 numerica...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.展开更多
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 proble...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.展开更多
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 ...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]）.展开更多
GraphX is a graph computing library based on Spark systems,where fault tolerance is a necessary guarantee for the high availability.However,the existing fault tolerance methods are mostly implemented in a pessimistic ...GraphX is a graph computing library based on Spark systems,where fault tolerance is a necessary guarantee for the high availability.However,the existing fault tolerance methods are mostly implemented in a pessimistic way and are aimed at general computing tasks.Considering the characteristics of iterative computation,this paper presents a combination method of the optimistic fault tolerance and checkpoint for recovering the data under different failure conditions.Firstly,for single node failure,we propose the optimistic fault tolerance mechanism based on compensation function.It does not add fault tolerance measures in advance and will not incur additional costs when there are no failures.Secondly,for multiple node failures,we propose the automatic checkpoint management strategy based on RDD importance.It comprehensively considers the factors of lineage length of RDD,dependency relationship,and computation time of RDD,which can set the RDD as the checkpoint properly.Finally,we implement our proposals in GraphX of Spark−3.5.1,and evaluate the performance by using representative iterative graph algorithms on the high performance computing cluster.The results verify the correctness of iteration results of the mechanism,and illustrate that when recovering the RDD partition,the job execution time can be reduced by the mechanism and strategy substantially.展开更多
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 th...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.展开更多
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 scena...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.展开更多
文摘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.
基金Supported by the National Natural Science Foundation of China (60970016,61173032)
文摘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.
文摘As a fundamental and effective tool for document understanding and organization, multi-document summarization enables better information services by creating concise and informative reports for large collections of documents. In this paper, we propose a sentence-word two layer graph algorithm combining with keyword density to generate the multi-document summarization, known as Graph ＆ Keywordp. The traditional graph methods of multi-document summarization only consider the influence of sentence and word in all documents rather than individual documents. Therefore, we construct multiple word graph and extract right keywords in each document to modify the sentence graph and to improve the significance and richness of the summary. Meanwhile, because of the differences in the words importance in documents, we propose to use keyword density for the summaries to provide rich content while using a small number of words. The experiment results show that the Graph ＆ Keywordp method outperforms the state of the art systems when tested on the Duc2004 data set. Key words： multi-document, graph algorithm, keyword density, Graph ＆ Keywordp, Due2004
基金supported by the National Natural Science Foundation of China under Grant No.61372092the China National Science and Technology Major Projects on New Generation Broadband Wireless Mobile Communications Network under Grants No.2011ZX03005-004,No.2012ZX03001029-003,No.2012ZX03001008-003
文摘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.
基金supported by Shandong Provincial Key Research and Development Program of China(2021CXGC010107,2020CXGC010107)the Shandong Provincial Natural Science Foundation of China(ZR2020KF035)the New 20 Project of Higher Education of Jinan,China(202228017).
文摘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.
文摘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.
基金Ye YUAN is supported by the National Key R&D Program of China(Grant No.2022YFB2702100)the National Natural Science Foundation of China(NSFC)(Grant Nos.61932004,62225203,U21A20516)+5 种基金Hangxu JI is supported by the NSFC(Grant No.62402096)the Guangdong Basic and Applied Basic Research Foundation(Grant No.2023A1515110268)Yishu WANG is supported by the NSFC(Grant No.62302084)Yuliang MA is supported by the NSFC(Grant No.62002054)the Fundamental Research Funds for the Central Universities of China(Grant No.N2304014)the Liaoning Provincial Natural Science Foundation Joint Fund(Grant No.2023-MSBA-080).
文摘1Introduction Graph partitioning is essential for large-scale distributed graph processing,as partitioning strategies directly affect graph algorithm performance[1].To ensure reliability and scalability,many graphbased applications[2](e.g.,Facebook,Weibo)deploy their services over geo-distributed datacenters(DCs),posing challenges for existing partition methods.These methods may struggle with heterogeneity(e.g.,network bandwidth)or overlook structural properties(e.g.,community structure)during optimization.
基金supported in part by the Innovation Program for Quantum Science and Technology(No.2021ZD0302901)in part by the National Natural Science Foundation of China(Grant No.62272431).
文摘1 Introduction Estimating the number of triangles in a graph is a fundamental problem and has found applications in many fields.For example,in social network,it can help us understand how closely the local community structure and nodes in the network are in close proximity.In this paper,we address this problem in the framework of graph streaming algorithms,which has received significant attention due to the increasing need to analyze large-scale graph data efficiently[1–3].However,most of these algorithms are not robust or are limited to unweighted graphs.
基金Research supported by the Science Foundation of Shandong Province.
文摘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.
基金Supported by the Natural Science Foundation of the People’s Republic of China under Grant（11571252）
文摘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.
基金supported by Japan Ministry of Education,Sciences and Culture(C21560471)the National Natural Science Foundation of China(61603268)+1 种基金the Research Project Supported by Shanxi Scholarship Council of China(2015-044)the Fundamental Research Project of Shanxi Province(2015021085)
文摘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.
文摘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.
基金National Natural Science Foundation of China(No.61272432)Qingdao Science and Technology Development Plan(No.12-1-4-6-(10)-jch)
文摘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.
基金funded by the Joint Funds of the National Natural Science Foundation of China (61079001)
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China (Nos. 61070224, 61232001, and 61173051)the China Postdoctoral Science Foundation (No. 2012M521551)
文摘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.
基金supported by a GermanNorwegian PPP grantsupported by the Indo-German Max Planck Center for Computer Science (IMPECS)
文摘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]）.
基金supported by the National Key Research and Development Program of China(Grant No.2021YFB0301200)the Hunan Natural Science Foundation Project(Grant No.2023JJ40555)+1 种基金the Hunan Provincial Graduate Student Research and Innovation Project(Grant No.LXBZZ2024035)the Hunan Provincial Department of Education Scientific Research Project(Grant No.22B0451).
文摘GraphX is a graph computing library based on Spark systems,where fault tolerance is a necessary guarantee for the high availability.However,the existing fault tolerance methods are mostly implemented in a pessimistic way and are aimed at general computing tasks.Considering the characteristics of iterative computation,this paper presents a combination method of the optimistic fault tolerance and checkpoint for recovering the data under different failure conditions.Firstly,for single node failure,we propose the optimistic fault tolerance mechanism based on compensation function.It does not add fault tolerance measures in advance and will not incur additional costs when there are no failures.Secondly,for multiple node failures,we propose the automatic checkpoint management strategy based on RDD importance.It comprehensively considers the factors of lineage length of RDD,dependency relationship,and computation time of RDD,which can set the RDD as the checkpoint properly.Finally,we implement our proposals in GraphX of Spark−3.5.1,and evaluate the performance by using representative iterative graph algorithms on the high performance computing cluster.The results verify the correctness of iteration results of the mechanism,and illustrate that when recovering the RDD partition,the job execution time can be reduced by the mechanism and strategy substantially.
文摘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.
基金National Natural Science Foundation of China(Grant Nos.61972444,61825202,62072195,and 61832006)Zhejiang Lab(2022P10AC02).
文摘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.
