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.展开更多
For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation (BP) algorithm. ...For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation (BP) algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.展开更多
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.展开更多
Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph...Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant's heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.展开更多
Unstructured and irregular graph data causes strong randomness and poor locality of data accesses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and proposes a branch-alternation-re...Unstructured and irregular graph data causes strong randomness and poor locality of data accesses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and proposes a branch-alternation-resorting algorithm(BAR).In order to make the algorithm run in parallel and improve the efficiency of algorithm operation,the BAR algorithm is mapped onto the reconfigurable array processor(APR-16)to achieve vertex reordering,effectively improving the locality of graph data.This paper validates the BAR algorithm on the GraphBIG framework,by utilizing the reordered dataset with BAR on breadth-first search(BFS),single source shortest paht(SSSP)and betweenness centrality(BC)algorithms for traversal.The results show that compared with DBR and Corder algorithms,BAR can reduce execution time by up to 33.00%,and 51.00%seperatively.In terms of data movement,the BAR algorithm has a maximum reduction of 39.00%compared with the DBR algorithm and 29.66%compared with Corder algorithm.In terms of computational complexity,the BAR algorithm has a maximum reduction of 32.56%compared with DBR algorithm and53.05%compared with Corder algorithm.展开更多
Evolutionary computation techniques have mostly been used to solve various optimization problems,and it is well known that graph isomorphism problem(GIP)is a nondeterministic polynomial problem.A simulated annealing(S...Evolutionary computation techniques have mostly been used to solve various optimization problems,and it is well known that graph isomorphism problem(GIP)is a nondeterministic polynomial problem.A simulated annealing(SA)algorithm for detecting graph isomorphism is proposed,and the proposed SA algorithm is well suited to deal with random graphs with large size.To verify the validity of the proposed SA algorithm,simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5,0.1,and 0.01,respectively.The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that...Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.展开更多
To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of ...To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of clustering algorithm has to be improved with the refinement algorithm application. The experiment result demonstrated that the multilevel graph text clustering algorithm is available. Key words text clustering - multilevel coarsen graph model - refinement algorithm - high-dimensional clustering CLC number TP301 Foundation item: Supported by the National Natural Science Foundation of China (60173051)Biography: CHEN Jian-bin(1970-), male, Associate professor, Ph. D., research direction: data mining.展开更多
In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify pat...In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.展开更多
电力系统的安全稳定运行是保障国家能源安全和经济发展的关键,而这在很大程度上依赖于对电力物联设备故障的准确预测。当前,随着电力物联网技术的发展,大量的数据被采集,但这些数据的潜在价值尚未得到充分挖掘,这在一定程度上限制了故...电力系统的安全稳定运行是保障国家能源安全和经济发展的关键,而这在很大程度上依赖于对电力物联设备故障的准确预测。当前,随着电力物联网技术的发展,大量的数据被采集,但这些数据的潜在价值尚未得到充分挖掘,这在一定程度上限制了故障预测的准确性,影响了电力系统的可靠运行。针对这一问题,该文提出了一种创新的基于GraphSAGE(Graph Sample and Aggregate)算法的电力物联设备故障预测。该方法通过PowerGraph数据集,将电力物联设备故障场景细分为四类,利用GraphSAGE模型的特性,深入学习和分析节点特征与边特征,从而实现对物联设备故障的有效预测。实验结果表明,该方法准确率达到97.5%,相较于其它传统方法,准确率提高了0.39%~6.21%,同时GraphSAGE模型实现了快速训练。该方法为电力物联设备安全稳定运行提供重要决策支持,能够对动态和相互联系的复杂系统进行更精细的分析,并增强电力系统运营部门对潜在干扰的预见和应对能力。展开更多
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.展开更多
The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method,...The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O(m) time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.展开更多
After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algo...After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algorithm. The code-series (CS) have the holo-information nature, so that both the content and the sign of each gain-term can be determined via the coded method. The principle of this method is simple and it is suited for computer programming. The capability of the computer-aided analysis for switched current network (SIN) can be enhanced.展开更多
Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associa...Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associated with subgraph mining in today’s on-demand system.To address this downside,our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs(BCCA-LSDG).The two-fold process is handled in the proposed BCCA-LSDG:graph indexing and authenticated query search(query processing).A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture.To resolve the issues and provide safe big data transmission,the proposed technique also combines blockchain with a consensus algorithm architecture.Security of the big data is ensured by dividing the BC network into distinct networks,each with a restricted number of allowed entities,data kept in the cloud gate server,and data analysis in the blockchain.The consensus algorithm is crucial for maintaining the speed,performance and security of the blockchain.Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets.Finally,the graph index refinement process is undertaken to improve the query results.Concerning query error,fuzzy logic is used to refine the index of the graph dynamically.The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems,and the combination of blockchain and subgraph provides a secure communication platform,according to the findings.展开更多
Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investme...Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investments required to deploy these networks, particularly related to the cost of equipment (optical fibers, transponders and multiplexers), the optimization of bandwidth and dynamic allocation of resources is essential to control operating costs and ensure continuity of service. Automatic switching technology for optical networks brings intelligence to the control plane to fully facilitate bandwidth utilization, traffic redirection, and automatic configuration of end-to-end services. This paper considers a local network operator’s WDM network without the implementation of the automatic switching technology, develops a network modeling software platform called Graphic Networks and using graph theory integrates a particularity of the automatic switching technology, which is the automatic rerouting of traffic in case of incident in the network. The incidents considered here are those links or route failures and node failures.展开更多
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linea...This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict ...This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict relationships between elements of a ring that multiply to zero. The paper explores the development and implementation of algorithms in MAPLE for constructing these ZDGs. The comparative study aims to discern the strengths, limitations, and computational efficiency of different MAPLE algorithms for creating zero divisor graphs offering insights for mathematicians, researchers, and computational enthusiasts involved in ring theory and mathematical computations.展开更多
基金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.
基金Project supported by the National Natural Science Foundation of China(Grant No.60972046)Grant from the National Defense Pre-Research Foundation of China
摘要For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation (BP) algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.
基金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.
基金the International Cooperation Project of Ministry of Science and Technology of P. R. China (GrantNo.CB7-2-01)SEC E-Institute: Shanghai High Institutions Grid
摘要Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration (VLSI) design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant's heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute (ANSI) C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.
基金the National Key R&D Program of China(No.2022ZD0119001)the National Natural Science Foundation of China(No.61834005)+3 种基金the Shaanxi Province Key R&D Plan(No.2022GY-027)the Key Scientific Research Project of Shaanxi Department of Education(No.22JY060)the Education Research Project of XUPT(No.JGA202108)the Graduate Student Innovation Fund of Xi'an University of Posts and Telecommunications(No.CXJJZL2022011)。
摘要Unstructured and irregular graph data causes strong randomness and poor locality of data accesses in graph processing.This paper optimizes the depth-branch-resorting algorithm(DBR),and proposes a branch-alternation-resorting algorithm(BAR).In order to make the algorithm run in parallel and improve the efficiency of algorithm operation,the BAR algorithm is mapped onto the reconfigurable array processor(APR-16)to achieve vertex reordering,effectively improving the locality of graph data.This paper validates the BAR algorithm on the GraphBIG framework,by utilizing the reordered dataset with BAR on breadth-first search(BFS),single source shortest paht(SSSP)and betweenness centrality(BC)algorithms for traversal.The results show that compared with DBR and Corder algorithms,BAR can reduce execution time by up to 33.00%,and 51.00%seperatively.In terms of data movement,the BAR algorithm has a maximum reduction of 39.00%compared with the DBR algorithm and 29.66%compared with Corder algorithm.In terms of computational complexity,the BAR algorithm has a maximum reduction of 32.56%compared with DBR algorithm and53.05%compared with Corder algorithm.
基金the National Natural Science Foundation of China(60373089,60674106,and 60533010)the National High Technology Research and Development"863"Program(2006AA01Z104)
摘要Evolutionary computation techniques have mostly been used to solve various optimization problems,and it is well known that graph isomorphism problem(GIP)is a nondeterministic polynomial problem.A simulated annealing(SA)algorithm for detecting graph isomorphism is proposed,and the proposed SA algorithm is well suited to deal with random graphs with large size.To verify the validity of the proposed SA algorithm,simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5,0.1,and 0.01,respectively.The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
基金supported by the National Science Foundation for Distinguished Young Scholars of China(Grant Nos.61003082 and 60903059)the National Natural Science Foundation of China(Grant No.60873014)the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(Grant No.60921062)
摘要Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.
摘要To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of clustering algorithm has to be improved with the refinement algorithm application. The experiment result demonstrated that the multilevel graph text clustering algorithm is available. Key words text clustering - multilevel coarsen graph model - refinement algorithm - high-dimensional clustering CLC number TP301 Foundation item: Supported by the National Natural Science Foundation of China (60173051)Biography: CHEN Jian-bin(1970-), male, Associate professor, Ph. D., research direction: data mining.
基金Supported by the National Natural Science Foundation of China (601133010)
摘要In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.
摘要电力系统的安全稳定运行是保障国家能源安全和经济发展的关键,而这在很大程度上依赖于对电力物联设备故障的准确预测。当前,随着电力物联网技术的发展,大量的数据被采集,但这些数据的潜在价值尚未得到充分挖掘,这在一定程度上限制了故障预测的准确性,影响了电力系统的可靠运行。针对这一问题,该文提出了一种创新的基于GraphSAGE(Graph Sample and Aggregate)算法的电力物联设备故障预测。该方法通过PowerGraph数据集,将电力物联设备故障场景细分为四类,利用GraphSAGE模型的特性,深入学习和分析节点特征与边特征,从而实现对物联设备故障的有效预测。实验结果表明,该方法准确率达到97.5%,相较于其它传统方法,准确率提高了0.39%~6.21%,同时GraphSAGE模型实现了快速训练。该方法为电力物联设备安全稳定运行提供重要决策支持,能够对动态和相互联系的复杂系统进行更精细的分析,并增强电力系统运营部门对潜在干扰的预见和应对能力。
基金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.
基金Supported by the National Natural Science Foundation of China(Grant No.11271365)the Domestic Senior Visiting Scholar Program in Higher Occupation Colleges in Jiangsu Province(Grant No.2014FX075)
摘要The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O(m) time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.
摘要After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algorithm. The code-series (CS) have the holo-information nature, so that both the content and the sign of each gain-term can be determined via the coded method. The principle of this method is simple and it is suited for computer programming. The capability of the computer-aided analysis for switched current network (SIN) can be enhanced.
摘要Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associated with subgraph mining in today’s on-demand system.To address this downside,our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs(BCCA-LSDG).The two-fold process is handled in the proposed BCCA-LSDG:graph indexing and authenticated query search(query processing).A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture.To resolve the issues and provide safe big data transmission,the proposed technique also combines blockchain with a consensus algorithm architecture.Security of the big data is ensured by dividing the BC network into distinct networks,each with a restricted number of allowed entities,data kept in the cloud gate server,and data analysis in the blockchain.The consensus algorithm is crucial for maintaining the speed,performance and security of the blockchain.Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets.Finally,the graph index refinement process is undertaken to improve the query results.Concerning query error,fuzzy logic is used to refine the index of the graph dynamically.The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems,and the combination of blockchain and subgraph provides a secure communication platform,according to the findings.
摘要Optical transport networks are now the basic infrastructure of modern communications systems, including the SDH and WDM backbone network of local network operators, in the case of Cameroon. Given the colossal investments required to deploy these networks, particularly related to the cost of equipment (optical fibers, transponders and multiplexers), the optimization of bandwidth and dynamic allocation of resources is essential to control operating costs and ensure continuity of service. Automatic switching technology for optical networks brings intelligence to the control plane to fully facilitate bandwidth utilization, traffic redirection, and automatic configuration of end-to-end services. This paper considers a local network operator’s WDM network without the implementation of the automatic switching technology, develops a network modeling software platform called Graphic Networks and using graph theory integrates a particularity of the automatic switching technology, which is the automatic rerouting of traffic in case of incident in the network. The incidents considered here are those links or route failures and node failures.
摘要This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.
摘要The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
摘要This research investigates the comparative efficacy of generating zero divisor graphs (ZDGs) of the ring of integers ℤn modulo n using MAPLE algorithm. Zero divisor graphs, pivotal in the study of ring theory, depict relationships between elements of a ring that multiply to zero. The paper explores the development and implementation of algorithms in MAPLE for constructing these ZDGs. The comparative study aims to discern the strengths, limitations, and computational efficiency of different MAPLE algorithms for creating zero divisor graphs offering insights for mathematicians, researchers, and computational enthusiasts involved in ring theory and mathematical computations.