In this paper we obtain a criterion under which the bijectivity of the canonical morphism of a weak Galois extension associated to a weak invertible entwining structure is equivalent to the existence of a strong conne...In this paper we obtain a criterion under which the bijectivity of the canonical morphism of a weak Galois extension associated to a weak invertible entwining structure is equivalent to the existence of a strong connection form. Also we obtain an explicit formula for a strong connection under equivariant projective conditions or under coseparability conditions.展开更多
Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a rev...Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.展开更多
Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix...Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix A_(α)(D),which is defined as Aα(D)=αW(D)+(1−α)A(D),0≤α≤1.The spectral radius of A_(α)(D)is called the Aαspectral radius of D,denoted byλα(D).We obtain some upper bounds on the Aαspectral radius of strongly connected irregular weighted digraphs.展开更多
In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems ha...In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems have been studied for disturbances with an exactly known exosystem.Compared with the existing results of high-order integrator dynamics,which can only handle sinusoidal disturbances with known frequencies,this paper aims to handle multi-tone disturbances with unknown frequencies by introducing an adaptive control technique to estimate the unknown frequencies.Technically,when the exosystem is known,the disturbance can be dealt with by the Luenburger observer.In contrast,the Luenburger observer cannot deal with an uncertain exosystem.The authors combine the internal model design and some adaptive control technique to solve the proposed problem.Further,the authors also establish the sufficient condition to guarantee the convergence of the estimated unknown frequencies to the actual values of these frequencies.Two examples are given to verify the proposed algorithm.展开更多
The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study propose...The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study proposes a DP algorithm based on node block sequence constraints.The proposed algorithm constrains the traversal process of the parent graph by using the M-sequence matrix to considerably reduce the time consumption and space complexity by pruning the traversal process of the order graph using the node block sequence.Experimental results show that compared with existing DP algorithms,the proposed algorithm can obtain learning results more efficiently with less than 1%loss of accuracy,and can be used for learning larger-scale networks.展开更多
Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This st...Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This study addresses this gap by developing specialized incremental SCC detection methods.We first leverage distinct edge types inherent in citation graphs to devise partition and local topological ordering strategies,minimizing redundant graph traversals.Based on this,we introduce two efficient bounded incremental algorithms:one for continuous single updates via dynamic maintenance of partitions and order,and the other for batch updates that further reduces edge traversals by building upon the single-update technique.Experimental evaluations on real-world citation graphs verify significant efficiency improvements,with our single incremental method achieving speedups of at least 11.5 times,and the batch incremental method achieving speedups of at least 5.0 times compared with baseline methods.展开更多
Metropolitan areas under different regional contexts show different development characteristics and evolution paths.Urban agglomeration of the Pearl River Delta is characterized by having multiple cores and strong con...Metropolitan areas under different regional contexts show different development characteristics and evolution paths.Urban agglomeration of the Pearl River Delta is characterized by having multiple cores and strong connection,in which cities used to be "geographically connected before interactive with each other." And during the functional interaction,three metropolitan areas emerged in different stages with different characteristics in the Pearl River Delta.By analyzing the urbanization process of the Pearl River Delta,it shows that the interaction among cities within the three metropolitan areas has obvious characteristics.In the early stage,it was featured by the industrial expansion benefiting from infrastructure integration.And then it was shifted to the co-construction and sharing of public services based on the demand of "people." Now it is in a new stage of spatial reconstruction driven by agglomeration of service industries and innovation forces.Finally,the lessons learned from the Pearl River Delta are summarized from the aspects of transportation,mechanism,shared value,relationship,and topography.展开更多
This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the act...This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the actions of all players in their action sets all the time,one has to resort to the projected gradient-based method.Under the assumption that the unique Nash equilibrium is the unique equilibrium of the pseudogradient system,an algorithm is proposed that is able to exponentially find the Nash equilibrium.Further,the authors also consider the distributed Nash equilibrium seeking problem for games whose actions are governed by high-order integrator dynamics and belong to some compact sets.Two examples are used to illustrate the proposed approach.展开更多
AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivi...AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivity C, then n≤c(d_k-d)/(d-1)M+d+1. It improves the previous knownresults, and it, in fact, is the best possible for several interesting cases. A similar result for arcconnectivity is also established.展开更多
Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(G)iff e and f are adjacent in G but do not span a triangle in G.The Gallai...Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(G)iff e and f are adjacent in G but do not span a triangle in G.The Gallai chromatic number of G,denoted by χ^(Γ)(G),is defined to be the chromatic number of Γ(G).It is known that the problem for determining χ^(Γ)(G)is NP-complete for a general graph G.In this paper,we study the Gallai chromatic number of graphs and relate our research with some parameters about edge coloring of graphs,such as PC number,SPC number,as well as chromatic index.For the(k,r)-star,we determine its PC number,SPC number,Gallai chromatic number,and chromatic index,and show that these parameters differ considerably in a sense.Then we show that the problem for determining χ^(Γ)(G)is still NP-complete even when G is a 3-regular graph,a near-complete graph or a chordal graph of diameter 5.Our result also implies that the problem for determining the SPC number of a graph G is NP-complete when G is a chordal graph of diameter 5.展开更多
In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, li...In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, linear systems with algebraic constraints are considered, and the corresponding results about consensus and average-consensus are derived. Then r-consensus and consensus problems of singular systems are investigated. Sufficient conditions of r-consensus and consensus are obtained,respectively. Finally, an illustrative example is given to show the effectiveness of the proposed method.展开更多
SIN(Space Information Network)has recently emerged as a promising approach to solving the collaboration difficulty among current space programs.However,because of the SIN’s large scale,high component complexity,and d...SIN(Space Information Network)has recently emerged as a promising approach to solving the collaboration difficulty among current space programs.However,because of the SIN’s large scale,high component complexity,and dynamic characteristics,designing a proper SIN architecture is challenging.Firstly,we propose a novel SIN architecture,which is composed of GEO(Geostationary Earth Orbit)satellites as backbone network nodes,LEO(Low Earth Orbit)or other types of satellites as enhanced coverage nodes,and high-altitude platforms to meet the service requirements of emergency or hot-spot applications.Unlike most existing studies,the proposed architecture is AS(Autonomous-System)based.We decouple the complex SIN into simpler sub-networks using a hierarchical AS model.Then,we propose a topology control algorithm to minimize the time delay among sub-AS networks.We prove that the proposed algorithm achieves logical k-connectivity provided that the original physical topology has k-connectivity.Simulation results validate the theoretic analysis and effectiveness of the algorithm.展开更多
The reachability of a strongly connected network may be destroyed after link damage.Since many networds have directed links with the potential for reversal,the reachabilty may be restored by reversing the direction of...The reachability of a strongly connected network may be destroyed after link damage.Since many networds have directed links with the potential for reversal,the reachabilty may be restored by reversing the direction of links.In this paper,the reliability of a network that allows reversal of links is dis- cussed.展开更多
In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly co...In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.展开更多
基金Supported by Ministerio de Educació n, Xunta de Galicia and by FEDER (Grant Nos. MTM2010-15634,MTM2009-14464-C02-01, PGIDT07PXB322079PR)
文摘In this paper we obtain a criterion under which the bijectivity of the canonical morphism of a weak Galois extension associated to a weak invertible entwining structure is equivalent to the existence of a strong connection form. Also we obtain an explicit formula for a strong connection under equivariant projective conditions or under coseparability conditions.
文摘Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.
基金Supported by the National Natural Science Foundation of China (Grant No.12001434)The Natural Science Basic Research Program of Shaanxi Province (Grant No.2022JM-006)Chinese Universities Scientific Fund (Grant No.2452020021)
文摘Let D be a weighted digraph with n vertices in which each arc has been assigned a positive number.Let A(D)be the adjacency matrix of D and W(D)=diag(w_(1)^(+),w_(2)^(+),...,w_(n)^(+)).In this paper,we study the matrix A_(α)(D),which is defined as Aα(D)=αW(D)+(1−α)A(D),0≤α≤1.The spectral radius of A_(α)(D)is called the Aαspectral radius of D,denoted byλα(D).We obtain some upper bounds on the Aαspectral radius of strongly connected irregular weighted digraphs.
基金supported in part by the Research Grants Council of the Hong Kong Special Administration Region under Grant No.14201420in part by the National Natural Science Foundation of China under GrantNo.61973260.
文摘In this paper,the authors study the problem of distributed Nash equilibrium seeking of N-player games with high-order integrator dynamics subject to disturbances generated by an uncertain exosystem.Similar problems have been studied for disturbances with an exactly known exosystem.Compared with the existing results of high-order integrator dynamics,which can only handle sinusoidal disturbances with known frequencies,this paper aims to handle multi-tone disturbances with unknown frequencies by introducing an adaptive control technique to estimate the unknown frequencies.Technically,when the exosystem is known,the disturbance can be dealt with by the Luenburger observer.In contrast,the Luenburger observer cannot deal with an uncertain exosystem.The authors combine the internal model design and some adaptive control technique to solve the proposed problem.Further,the authors also establish the sufficient condition to guarantee the convergence of the estimated unknown frequencies to the actual values of these frequencies.Two examples are given to verify the proposed algorithm.
基金Shaanxi Science Fund for Distinguished Young Scholars,Grant/Award Number:2024JC-JCQN-57Xi’an Science and Technology Plan Project,Grant/Award Number:2023JH-QCYJQ-0086+2 种基金Scientific Research Program Funded by Education Department of Shaanxi Provincial Government,Grant/Award Number:P23JP071Engineering Technology Research Center of Shaanxi Province for Intelligent Testing and Reliability Evaluation of Electronic Equipments,Grant/Award Number:2023-ZC-GCZX-00472022 Shaanxi University Youth Innovation Team Project。
文摘The use of dynamic programming(DP)algorithms to learn Bayesian network structures is limited by their high space complexity and difficulty in learning the structure of large-scale networks.Therefore,this study proposes a DP algorithm based on node block sequence constraints.The proposed algorithm constrains the traversal process of the parent graph by using the M-sequence matrix to considerably reduce the time consumption and space complexity by pruning the traversal process of the order graph using the node block sequence.Experimental results show that compared with existing DP algorithms,the proposed algorithm can obtain learning results more efficiently with less than 1%loss of accuracy,and can be used for learning larger-scale networks.
基金supported by the National Natural Science Foundation of China under Grant Nos.61925203 and U22B2021.
文摘Strongly connected component(SCC)detection is fundamental for analyzing citation graphs,yet existing general-purpose algorithms inefficiently handle the dynamic nature and specific properties of these networks.This study addresses this gap by developing specialized incremental SCC detection methods.We first leverage distinct edge types inherent in citation graphs to devise partition and local topological ordering strategies,minimizing redundant graph traversals.Based on this,we introduce two efficient bounded incremental algorithms:one for continuous single updates via dynamic maintenance of partitions and order,and the other for batch updates that further reduces edge traversals by building upon the single-update technique.Experimental evaluations on real-world citation graphs verify significant efficiency improvements,with our single incremental method achieving speedups of at least 11.5 times,and the batch incremental method achieving speedups of at least 5.0 times compared with baseline methods.
文摘Metropolitan areas under different regional contexts show different development characteristics and evolution paths.Urban agglomeration of the Pearl River Delta is characterized by having multiple cores and strong connection,in which cities used to be "geographically connected before interactive with each other." And during the functional interaction,three metropolitan areas emerged in different stages with different characteristics in the Pearl River Delta.By analyzing the urbanization process of the Pearl River Delta,it shows that the interaction among cities within the three metropolitan areas has obvious characteristics.In the early stage,it was featured by the industrial expansion benefiting from infrastructure integration.And then it was shifted to the co-construction and sharing of public services based on the demand of "people." Now it is in a new stage of spatial reconstruction driven by agglomeration of service industries and innovation forces.Finally,the lessons learned from the Pearl River Delta are summarized from the aspects of transportation,mechanism,shared value,relationship,and topography.
基金supported in part by the Research Grants Council of the Hong Kong Special Administration Region under Grant No.14202619in part by the National Natural Science Foundation of China under Grant No.61973260。
文摘This paper studies the distributed Nash equilibrium seeking(DNES)problem for games whose action sets are compact and whose network graph is switching satisfying the jointly strongly connected condition.To keep the actions of all players in their action sets all the time,one has to resort to the projected gradient-based method.Under the assumption that the unique Nash equilibrium is the unique equilibrium of the pseudogradient system,an algorithm is proposed that is able to exponentially find the Nash equilibrium.Further,the authors also consider the distributed Nash equilibrium seeking problem for games whose actions are governed by high-order integrator dynamics and belong to some compact sets.Two examples are used to illustrate the proposed approach.
基金This project is supported by the National Natural Science Foundation of China
文摘AN INEQUALITY RELATING THE ORDER, MAXIMUM DEGREE, DIAMETER AND CONNECTIVITY OF A STRONGLY CONNECTED DIGRAPH We prove that if there is a strongly connected digraph of order n, maximum degree d,diameter k and connectivity C, then n≤c(d_k-d)/(d-1)M+d+1. It improves the previous knownresults, and it, in fact, is the best possible for several interesting cases. A similar result for arcconnectivity is also established.
基金supported by the National Natural Science Foundation of China(Nos.12071442 and 11971228)the Fundamental Research Funds for the Central Universities(No.020314380035).
文摘Given a graph G=(V,E),the Gallai graph of G,denoted by Γ(G),is the graph with vertex set E in which two edges e and f of G are adjacent in Γ(G)iff e and f are adjacent in G but do not span a triangle in G.The Gallai chromatic number of G,denoted by χ^(Γ)(G),is defined to be the chromatic number of Γ(G).It is known that the problem for determining χ^(Γ)(G)is NP-complete for a general graph G.In this paper,we study the Gallai chromatic number of graphs and relate our research with some parameters about edge coloring of graphs,such as PC number,SPC number,as well as chromatic index.For the(k,r)-star,we determine its PC number,SPC number,Gallai chromatic number,and chromatic index,and show that these parameters differ considerably in a sense.Then we show that the problem for determining χ^(Γ)(G)is still NP-complete even when G is a 3-regular graph,a near-complete graph or a chordal graph of diameter 5.Our result also implies that the problem for determining the SPC number of a graph G is NP-complete when G is a chordal graph of diameter 5.
基金supported by the National Natural Science Foundation of China under Grant Nos.61174141 and 61374025Research Awards Young and Middle-Aged Scientists of Shandong Province under Grant Nos.BS2011SF009 and BS2011DX019Excellent Youth Foundation of Shandong Province under Grant No.JQ201219
文摘In this paper, the problem of consensus for continuous time singular systems of multi-agent networks is considered. The definition of r-consensus is introduced for singular systems of multi-agent networks. Firstly, linear systems with algebraic constraints are considered, and the corresponding results about consensus and average-consensus are derived. Then r-consensus and consensus problems of singular systems are investigated. Sufficient conditions of r-consensus and consensus are obtained,respectively. Finally, an illustrative example is given to show the effectiveness of the proposed method.
基金supported by the National Natural Science Foundation of China(Nos.91338201,91438109,61401507).
文摘SIN(Space Information Network)has recently emerged as a promising approach to solving the collaboration difficulty among current space programs.However,because of the SIN’s large scale,high component complexity,and dynamic characteristics,designing a proper SIN architecture is challenging.Firstly,we propose a novel SIN architecture,which is composed of GEO(Geostationary Earth Orbit)satellites as backbone network nodes,LEO(Low Earth Orbit)or other types of satellites as enhanced coverage nodes,and high-altitude platforms to meet the service requirements of emergency or hot-spot applications.Unlike most existing studies,the proposed architecture is AS(Autonomous-System)based.We decouple the complex SIN into simpler sub-networks using a hierarchical AS model.Then,we propose a topology control algorithm to minimize the time delay among sub-AS networks.We prove that the proposed algorithm achieves logical k-connectivity provided that the original physical topology has k-connectivity.Simulation results validate the theoretic analysis and effectiveness of the algorithm.
文摘The reachability of a strongly connected network may be destroyed after link damage.Since many networds have directed links with the potential for reversal,the reachabilty may be restored by reversing the direction of links.In this paper,the reliability of a network that allows reversal of links is dis- cussed.
基金Supported by NSFC(Grant No.10771225)Fundamental Research Funds for the Central University
文摘In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a ∏-contractible directed cycle of G, then both of Int（C,∏） and Ext（C,∏） are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface Sg with fw（G） ≥ 2（fw（G） is the face-width of G）, then any cycle base of G must contain at least 2g noncontractible directed cycles; if G has been embedded in non-orientable surface Ng, then any cycle base of G must contain at least g noncontractible directed cycles.
