In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{...In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？展开更多
A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorizat...A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.展开更多
Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k...Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k</sub> and S<sub>k</sub> denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph has a -decomposition if and only if k is even, and .展开更多
The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous kn...The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.展开更多
cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2.A quadrilateral with four multiedges is called heavy-quadrilateral.It is proved that if th...cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2.A quadrilateral with four multiedges is called heavy-quadrilateral.It is proved that if the minimum degree of M is at least 6k-2,then M contains k vertex-disjoint quadrilaterals,such that k-1 of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges,with only three exceptions.展开更多
LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. W...LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m + n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m + n)] is an integer.展开更多
LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλ...LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.展开更多
Let λK m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P v-factorization of λK m,n is a set of edge-disjoint P v-factors of λK m,n which partition the set of edges of λ...Let λK m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P v-factorization of λK m,n is a set of edge-disjoint P v-factors of λK m,n which partition the set of edges of λK m,n . When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P v-factorization of λK m,n . When v is an odd number, we have proposed a conjecture. Very recently, we have proved that the conjecture is true when v = 4k ? 1. In this paper we shall show that the conjecture is true when v = 4k + 1, and then the conjecture is true. That is, we will prove that the necessary and sufficient conditions for the existence of a P 4k+1-factorization of λK m,n are (1) 2km ? (2k + 1)n, (2) 2kn ? (2k + 1)m, (3) m + n ≡ 0 (mod 4k + 1), (4) λ(4k + 1)mn/[4k(m + n)] is an integer.展开更多
In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows： let G（n; {pk}） be the probability space of all the labelled loopless multigraphs with vertex set...In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows： let G（n; {pk}） be the probability space of all the labelled loopless multigraphs with vertex set V = {v1, v2, ..., vn }, in which the distribution of tvi,vj, the number of the edges between any two vertices vi and vj is P{tvi,vj =k}=Pk, k=0, 1,2,...and they are independent of each other. Denote by Xd = Xd（G）,Yd = Yd（G）, Zd = Zd（G） and Zcd = Zcd（G） the number of vertices of G with degree d, at least d, at most d and between c and d. In this paper, we discuss the distribution of Xd, Yd, Zd and Zcd in the probability space G（n; （Pk））.展开更多
While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph...While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.展开更多
Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a v...Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.展开更多
A multi-GPU system designed for high-speed,real-time signal processing of optical coherencetomography(OCT)is described herein.For the OCT data sampled in linear wave numbers,themaximum procesing rates reached 2.95 MHz...A multi-GPU system designed for high-speed,real-time signal processing of optical coherencetomography(OCT)is described herein.For the OCT data sampled in linear wave numbers,themaximum procesing rates reached 2.95 MHz for 1024-OCT and 1.96 MHz for 2048-OCT.Data sampled using linear wavelengths were re-sampled using a time-domain interpolation method and zero-padding interpolation method to improve image quality.The maximum processing rates for1024-OCT reached 2.16 MHz for the time-domain method and 1.26 MHz for the zero-paddingmethod.The maximum processing rates for 2048-0CT reached_1.58 MHz,and 0.68 MHz,respectively.This method is capable of high-speed,real-time processing for O CT systems.展开更多
Trajectory prediction for heterogeneous traffic agents plays a crucial role in ensuring the safety and efficiency of automated driving in highly interactive traffic environments.Numerous studies in this area have focu...Trajectory prediction for heterogeneous traffic agents plays a crucial role in ensuring the safety and efficiency of automated driving in highly interactive traffic environments.Numerous studies in this area have focused on physicsbased approaches because they can clearly interpret the dynamic evolution of trajectories.However,physics-based methods often suffer from limited accuracy.Recent learning-based methods have demonstrated better performance,but they cannot be fully trusted due to the insufficient incorporation of physical constraints.To mitigate the limitations of purely physics-based and learning-based approaches,this study proposes a kinematics-aware multigraph attention network(KAMGAT)that incorporates physics models into a deep learning framework to improve the learning process of neural networks.Besides,we propose a residual prediction module to further refine the trajectory predictions and address the limitations arising from simplified assumptions in kinematic models.We evaluate our proposed model through experiments on two challenging trajectory datasets,namely,ApolloScape and NGSIM.Our findings from the experiments demonstrate that our model outperforms various kinematics-agnostic models with respect to prediction accuracy and learning efficiency.展开更多
Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate...Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.展开更多
Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where...Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where ve,ve′are two new vertices not in V(G).If e=e′,then G(e,e′),also denoted by G(e),is obtained from G by replacing e=u1v1 with a path u1vev1.A graph G is strongly spanning trailable if for any e,e′∈E(G),G(e,e′)has a spanning(ve,ve′)-trail.The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties.A sequence d=(d1,d2,⋯,dn)is multigraphic if there is a multigraph G with degree sequence d,and such a graph G is called a realization of d.A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph,and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected.In this paper,we prove that a nonincreasing multigraphic sequence d=(d1,d2)⋯,dn)is strongly spanning trailable if and only if either n=1 and d1=0 or n≥2 and dn≥3.Applying this result,we prove that for a nonincreasing multigraphic sequence d=(d1,d2,⋯,dn),if n≥2 and dn≥3,then d is line-hamiltonian-connected.展开更多
文摘In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows：let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a_1,a_2,...,a_n} and B = {b_1,b_2,...,b_m}, in which the numbers t_（ai）,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_（ai）,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_（c,d,A）, the number of vertices in A with degree between c and d of G_（n,m）∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_（n,m）∈ζ（n,m;{pk}） has maximum degree D（n）in A？ under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A？
基金the National Natural Science Foundation of China (10571133)
文摘A K1,k-factorization of λKm,n is a set of edge-disjoint K1,k-factors of λKm,n, which partition the set of edges of λKm,n. In this paper, it is proved that a sufficient condition for the existence of K1,k-factorization of λKm,n, whenever k is any positive integer, is that （1） m ≤ kn, （2） n ≤ km, （3） km-n = kn-m ≡ 0 （mod （k^2- 1）） and （4） λ（km-n）（kn-m） ≡ 0 （mod k（k- 1）（k^2 - 1）（m ＋ n））.
文摘Let be a family of subgraphs of a graph G. An L-decomposition of G is an edge-disjoint decomposition of G into positive integer copies of H<sub>i</sub>, where . Let C<sub>k</sub>, P<sub>k</sub> and S<sub>k</sub> denote a cycle, a path and a star with k edges, respectively. For an integer , we prove that a balanced complete bipartite multigraph has a -decomposition if and only if k is even, and .
文摘The lower bounds on the maximum genus of loopless graphs are obtained according to the connectivity of these graphs. This not only answers a question of Chen, Archdeacon and Gross, but also generalizes the previous known results. Thus, a picture of the lower bounds on the maximum genus of loopless multigraphs is presented.
文摘cycle of length 4 is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most 2.A quadrilateral with four multiedges is called heavy-quadrilateral.It is proved that if the minimum degree of M is at least 6k-2,then M contains k vertex-disjoint quadrilaterals,such that k-1 of them are heavy-quadrilaterals and the remaining one is a quadrilateral with three multiedges,with only three exceptions.
基金This work was supported by the National Natural Science Foundation of China (Grant No. 10571133).
文摘LetλKm,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A Pν-factorization ofλKm,n is a set of edge-disjoint Pν-factors ofλKm,n which partition the set of edges ofλKm,n. Whenνis an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a Pν-factorization ofλKm,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true forν= 3. In this paper we will show that the conjecture is true whenν= 4k-1. That is, we shall prove that a necessary and sufficient condition for the existence of a P4k-1-factorization ofλKm,n is (1) (2k-1)m≤2kn, (2) (2k-1)n≤2km, (3)m + n = 0 (mod 4k-1), (4)λ(4k-1)mn/[2(2k-1)(m + n)] is an integer.
基金supported by the National Natural Science Foundation of China (Grant No.K110703711)。
文摘LetλK_(m,n)be a complete bipartite multigraph with two partite sets having m and n vertices,respectively.A K_(p,q)-factorization ofλK_(m,n)is a set of K_(p,q)-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).Whenλ=1,Martin,in[Complete bipartite factorizations by complete bipartite graphs,Discrete Math.,167/168(1997),461–480],gave simple necessary conditions for such a factorization to exist,and conjectured those conditions are always sufficient.In this paper,we will study the K_(p,q)-factorization ofλK_(m,n)for p=1,to show that the necessary conditions for such a factorization are always sufficient whenever related parameters are sufficiently large.
基金This work was supported by the National Natural Science Foundation of China(Grant No.10571133).
文摘Let λK m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P v-factorization of λK m,n is a set of edge-disjoint P v-factors of λK m,n which partition the set of edges of λK m,n . When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P v-factorization of λK m,n . When v is an odd number, we have proposed a conjecture. Very recently, we have proved that the conjecture is true when v = 4k ? 1. In this paper we shall show that the conjecture is true when v = 4k + 1, and then the conjecture is true. That is, we will prove that the necessary and sufficient conditions for the existence of a P 4k+1-factorization of λK m,n are (1) 2km ? (2k + 1)n, (2) 2kn ? (2k + 1)m, (3) m + n ≡ 0 (mod 4k + 1), (4) λ(4k + 1)mn/[4k(m + n)] is an integer.
基金Supported by National Natural Science Fund of China (Grant Nos. 10831001, 10871046, 10971027)Science and Technology of Science Fund of Fujian Province (Grant No. A0950059)Science and Technology Development Fund of Fuzhou University (Grant No. 2009-XQ-27)
文摘In this paper, as a generalization of the binomial random graph model, we define the model of multigraphs as follows： let G（n; {pk}） be the probability space of all the labelled loopless multigraphs with vertex set V = {v1, v2, ..., vn }, in which the distribution of tvi,vj, the number of the edges between any two vertices vi and vj is P{tvi,vj =k}=Pk, k=0, 1,2,...and they are independent of each other. Denote by Xd = Xd（G）,Yd = Yd（G）, Zd = Zd（G） and Zcd = Zcd（G） the number of vertices of G with degree d, at least d, at most d and between c and d. In this paper, we discuss the distribution of Xd, Yd, Zd and Zcd in the probability space G（n; （Pk））.
基金supported by the National Natural Science Fundation of China(61103081)
文摘While it is very reasonable to use a multigraph consisting of multiple edges between vertices to represent various relationships, the multigraph has not drawn much attention in research. To visualize such a multigraph, a clear layout representing a global structure is of great importance, and interactive visual analysis which allows the multiple edges to be adjusted in appropriate ways for detailed presentation is also essential. A novel interactive two-phase approach to visualizing and exploring multigraph is proposed. The approach consists of two phases： the first phase improves the previous popular works on force-directed methods to produce a brief drawing for the aggregation graph of the input multigraph, while the second phase proposes two interactive strategies, the magnifier model and the thematic-oriented subgraph model. The former highlights the internal details of an aggregation edge which is selected interactively by user, and draws the details in a magnifying view by cubic Bezier curves; the latter highlights only the thematic subgraph consisting of the selected multiple edges that the user concerns. The efficiency of the proposed approach is demonstrated with a real-world multigraph dataset and how it is used effectively is discussed for various potential applications.
基金The authors extend their appreciation to the Deanship of Scientific Research at King Khalid University for funding this work through the Large Group Research Project under grant number(R.G.P.2/181/44).
文摘Graph theory has a significant impact and is crucial in the structure of many real-life situations.To simulate uncertainty and ambiguity,many extensions of graph theoretical notions were created.Planar graphs play a vital role in modelling which has the property of non-crossing edges.Although crossing edges benefit,they have some drawbacks,which paved the way for the introduction of planar graphs.The overall purpose of the study is to contribute to the conceptual development of the Pythagorean Neutrosophic graph.The basic methodology of our research is the incorporation of the analogous concepts of planar graphs in the Pythagorean Neutrosophic graphs.The significant finding of our research is the introduction of Pythagorean Neutrosophic Planar graphs,a conceptual blending of Pythagorean Neutro-sophic and Planar graphs.The idea of Pythagorean Neutrosophic multigraphs and dual graphs are also introduced to deal with the ambiguous situations.This paper investigates the Pythagorean Neutrosophic planar values,which form the edges of the Pythagorean neutrosophic graphs.The concept of Pythagorean Neutrosophic dual graphs,isomorphism,co-weak and weak isomorphism have also been explored for Pythagorean Neutrosophic planar graphs.A decision-making algorithm was proposed with a numerical illustra-tion by using the Pythagorean Neutrosophic fuzzy graph.
基金the support from the union project of Peking University third hospital&Chinese Academy of Sciences(Grant No.7490-04,Grant No.KJZD-EW-TZ-L03)the Sichuan Youth Science&Technology Foundation(Grant No.13QNJJ0034)+1 种基金the West Light Foundation of the Chinese Academy of Sciences,the National Major Scientific Equipment program(Grant No.2012YQ120080)the National Science Foundation of China(Grant No.6118082).
文摘A multi-GPU system designed for high-speed,real-time signal processing of optical coherencetomography(OCT)is described herein.For the OCT data sampled in linear wave numbers,themaximum procesing rates reached 2.95 MHz for 1024-OCT and 1.96 MHz for 2048-OCT.Data sampled using linear wavelengths were re-sampled using a time-domain interpolation method and zero-padding interpolation method to improve image quality.The maximum processing rates for1024-OCT reached 2.16 MHz for the time-domain method and 1.26 MHz for the zero-paddingmethod.The maximum processing rates for 2048-0CT reached_1.58 MHz,and 0.68 MHz,respectively.This method is capable of high-speed,real-time processing for O CT systems.
基金the University of Wisconsin-Madison’s Center for Connected and Automated Transportation(CCAT),a part of the larger CCAT consortium,a USDOT Region 5 University Transportation Center funded by the U.S.Department of Transportation,Award#69A3552348305.
文摘Trajectory prediction for heterogeneous traffic agents plays a crucial role in ensuring the safety and efficiency of automated driving in highly interactive traffic environments.Numerous studies in this area have focused on physicsbased approaches because they can clearly interpret the dynamic evolution of trajectories.However,physics-based methods often suffer from limited accuracy.Recent learning-based methods have demonstrated better performance,but they cannot be fully trusted due to the insufficient incorporation of physical constraints.To mitigate the limitations of purely physics-based and learning-based approaches,this study proposes a kinematics-aware multigraph attention network(KAMGAT)that incorporates physics models into a deep learning framework to improve the learning process of neural networks.Besides,we propose a residual prediction module to further refine the trajectory predictions and address the limitations arising from simplified assumptions in kinematic models.We evaluate our proposed model through experiments on two challenging trajectory datasets,namely,ApolloScape and NGSIM.Our findings from the experiments demonstrate that our model outperforms various kinematics-agnostic models with respect to prediction accuracy and learning efficiency.
基金This work was supported by the UK Engineering and Physical Sciences Research Council(grant no.EP/N029496/1,EP/N029496/2,EP/N029356/1,EP/N029577/1,and EP/N029577/2)the joint scholarship of the China Scholarship Council and Queen Mary,University of London(grant no.202006830015).
文摘Efficient airport airside ground movement(AAGM)is key to successful operations of urban air mobility.Recent studies have introduced the use of multi-objective multigraphs(MOMGs)as the conceptual prototype to formulate AAGM.Swift calculation of the shortest path costs is crucial for the algorithmic heuristic search on MOMGs,however,previous work chiefly focused on single-objective simple graphs(SOSGs),treated cost enquires as search problems,and failed to keep a low level of computational time and storage complexity.This paper concentrates on the conceptual prototype MOMG,and investigates its node feature extraction,which lays the foundation for efficient prediction of shortest path costs.Two extraction methods are implemented and compared:a statistics-based method that summarises 22 node physical patterns from graph theory principles,and a learning-based method that employs node embedding technique to encode graph structures into a discriminative vector space.The former method can effectively evaluate the node physical patterns and reveals their individual importance for distance prediction,while the latter provides novel practices on processing multigraphs for node embedding algorithms that can merely handle SOSGs.Three regression models are applied to predict the shortest path costs to demonstrate the performance of each.Our experiments on randomly generated benchmark MOMGs show that(i)the statistics-based method underperforms on characterising small distance values due to severe overestimation;(ii)A subset of essential physical patterns can achieve comparable or slightly better prediction accuracy than that based on a complete set of patterns;and(iii)the learning-based method consistently outperforms the statistics-based method,while maintaining a competitive level of computational complexity.
基金This paper is supported by the National Natural Science Foundation of China(Nos.11771039,11971054)Fundamental Research Funds for the Central Universities of China(No.2015JBM107)the 111 Project of China(No.B16002)。
文摘Let G be a multigraph.Suppose that e=u1v1 and e′=u2v2 are two edges of G.If e≠e′,then G(e,e′)is the graph obtained from G by replacing e=u1v1 with a path u1vev1 and by replacing e′=u2v2 with a path u2ve′v2,where ve,ve′are two new vertices not in V(G).If e=e′,then G(e,e′),also denoted by G(e),is obtained from G by replacing e=u1v1 with a path u1vev1.A graph G is strongly spanning trailable if for any e,e′∈E(G),G(e,e′)has a spanning(ve,ve′)-trail.The design of n processor network with given number of connections from each processor and with a desirable strength of the network can be modelled as a degree sequence realization problem with certain desirable graphical properties.A sequence d=(d1,d2,⋯,dn)is multigraphic if there is a multigraph G with degree sequence d,and such a graph G is called a realization of d.A multigraphic degree sequence d is strongly spanning trailable if d has a realization G which is a strongly spanning trailable graph,and d is line-hamiltonian-connected if d has a realization G such that the line graph of G is hamiltonian-connected.In this paper,we prove that a nonincreasing multigraphic sequence d=(d1,d2)⋯,dn)is strongly spanning trailable if and only if either n=1 and d1=0 or n≥2 and dn≥3.Applying this result,we prove that for a nonincreasing multigraphic sequence d=(d1,d2,⋯,dn),if n≥2 and dn≥3,then d is line-hamiltonian-connected.
