Mathematics

Research

24 pages, 2433 KiB

Open AccessFeature PaperArticle

Generalized Shortest Path Problem: An Innovative Approach for Non-Additive Problems in Conditional Weighted Graphs

by Adrien Durand, Timothé Watteau, Georges Ghazi and Ruxandra Mihaela Botez

Mathematics 2024, 12(19), 2995; https://doi.org/10.3390/math12192995 - 26 Sep 2024

Viewed by 1090

The shortest path problem is fundamental in graph theory and has been studied extensively due to its practical importance. Despite this aspect, finding the shortest path between two nodes remains a significant challenge in many applications, as it often becomes complex and time [...] Read more.

The shortest path problem is fundamental in graph theory and has been studied extensively due to its practical importance. Despite this aspect, finding the shortest path between two nodes remains a significant challenge in many applications, as it often becomes complex and time consuming. This complexity becomes even more challenging when constraints make the problem non-additive, thereby increasing the difficulty of finding the optimal path. The objective of this paper is to present a broad perspective on the conventional shortest path problem. It introduces a new method to classify cost functions associated with graphs by defining distinct sets of cost functions. This classification facilitates the exploration of line graphs and an understanding of the upper bounds on the transformation sizes for these types of graphs. Based on these foundations, the paper proposes a practical methodology for solving non-additive shortest path problems. It also provides a proof of optimality and establishes an upper bound on the algorithmic cost of the proposed methodology. This study not only expands the scope of traditional shortest path problems but also highlights their computational complexity and potential solutions. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

18 pages, 374 KiB

Open AccessArticle

Combinatorial Generation Algorithms for Directed Lattice Paths

by Yuriy Shablya, Arsen Merinov and Dmitry Kruchinin

Mathematics 2024, 12(8), 1207; https://doi.org/10.3390/math12081207 - 17 Apr 2024

Viewed by 1035

Abstract

Graphs are a powerful tool for solving various mathematical problems. One such task is the representation of discrete structures. Combinatorial generation methods make it possible to obtain algorithms that can create discrete structures with specified properties. This article is devoted to issues related [...] Read more.

Graphs are a powerful tool for solving various mathematical problems. One such task is the representation of discrete structures. Combinatorial generation methods make it possible to obtain algorithms that can create discrete structures with specified properties. This article is devoted to issues related to the construction of such combinatorial generation algorithms for a wide class of directed lattice paths. The main method used is based on the representation of a given combinatorial set in the form of an AND/OR tree structure. To apply this method, it is necessary to have an expression for the cardinality function of a combinatorial set that satisfies certain requirements. As the main result, we have found recurrence relations for enumerating simple directed lattice paths that satisfy the requirements of the applied method and have constructed the corresponding AND/OR tree structure. Applying the constructed AND/OR tree structure, we have developed new algorithms for ranking and unranking simple directed lattice paths. Additionally, the obtained results were generalized to the case of directed lattice paths. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

16 pages, 1564 KiB

Open AccessArticle

Automatic Evaluation Method for Functional Movement Screening Based on a Dual-Stream Network and Feature Fusion

by Xiuchun Lin, Renguang Chen, Chen Feng, Zhide Chen, Xu Yang and Hui Cui

Mathematics 2024, 12(8), 1162; https://doi.org/10.3390/math12081162 - 12 Apr 2024

Cited by 2 | Viewed by 882

Abstract

Functional Movement Screening (FMS) is a movement pattern quality assessment system used to assess basic movement capabilities such as flexibility, stability, and pliability. Movement impairments and abnormal postures can be identified through peculiar movements and postures of the body. The reliability, validity, and [...] Read more.

Functional Movement Screening (FMS) is a movement pattern quality assessment system used to assess basic movement capabilities such as flexibility, stability, and pliability. Movement impairments and abnormal postures can be identified through peculiar movements and postures of the body. The reliability, validity, and accuracy of functional movement screening are difficult to test due to the subjective nature of the assessment. In this sense, this paper presents an automatic evaluation method for functional movement screening based on a dual-stream network and feature fusion. First, the RAFT algorithm is used to estimate the optical flow of a video, generating a set of optical flow images to represent the motion between consecutive frames. By inputting optical flow images and original video frames separately into the I3D model, it can better capture spatiotemporal features compared to the single-stream method. Meanwhile, this paper introduces a simple but effective attention fusion method that combines features extracted from optical flow with the original frames, enabling the network to focus on the most relevant parts of the input data, thereby improving prediction accuracy. The prediction of the four categories of FMS results was performed. It produced better correlation results compared to other more complex fusion protocols, with an accuracy improvement of 3% over the best-performing fusion method. Tests on public datasets showed that the evaluation metrics of the method proposed in this paper were the most advanced, with an accuracy improvement of approximately 4% compared to the currently superior methods. The use of deep learning methods makes it more objective and reliable to identify human movement impairments and abnormal postures. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

22 pages, 557 KiB

Open AccessArticle

Efficient Maintenance of Minimum Spanning Trees in Dynamic Weighted Undirected Graphs

by Mao Luo, Huigang Qin, Xinyun Wu, Caiquan Xiong, Dahai Xia and Yuanzhi Ke

Mathematics 2024, 12(7), 1021; https://doi.org/10.3390/math12071021 - 28 Mar 2024

Viewed by 1728

Abstract

This paper presents an algorithm for effectively maintaining the minimum spanning tree in dynamic weighted undirected graphs. The algorithm efficiently updates the minimum spanning tree when the underlying graph structure changes. By identifying the portion of the original tree that can be preserved [...] Read more.

This paper presents an algorithm for effectively maintaining the minimum spanning tree in dynamic weighted undirected graphs. The algorithm efficiently updates the minimum spanning tree when the underlying graph structure changes. By identifying the portion of the original tree that can be preserved in the updated tree, our algorithm avoids recalculating the minimum spanning tree from scratch. We provide proof of correctness for the proposed algorithm and analyze its time complexity. In general scenarios, the time complexity of our algorithm is comparable to that of Kruskal’s algorithm. However, the experimental results demonstrate that our algorithm outperforms the approach of recomputing the minimum spanning tree by using Kruskal’s algorithm, especially in medium- and large-scale dynamic graphs where the graph undergoes iterative changes. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

14 pages, 399 KiB

Open AccessFeature PaperArticle

A New Perspective on Moran’s Coefficient: Revisited

by Hiroshi Yamada

Mathematics 2024, 12(2), 253; https://doi.org/10.3390/math12020253 - 12 Jan 2024

Cited by 3 | Viewed by 1135

Abstract

Moran’s I (Moran’s coefficient) is one of the most prominent measures of spatial autocorrelation. It is well known that Moran’s I has a representation that is similar to a Fourier series and is therefore useful for characterizing spatial data. However, the representation needs [...] Read more.

Moran’s I (Moran’s coefficient) is one of the most prominent measures of spatial autocorrelation. It is well known that Moran’s I has a representation that is similar to a Fourier series and is therefore useful for characterizing spatial data. However, the representation needs to be modified. This paper contributes to the literature by showing the necessary modification and presenting some further results. In addition, we provide the required MATLAB/GNU Octave and R user-defined functions. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

7 pages, 337 KiB

Open AccessArticle

Geary’s c and Spectral Graph Theory: A Complement

by Hiroshi Yamada

Mathematics 2023, 11(20), 4228; https://doi.org/10.3390/math11204228 - 10 Oct 2023

Cited by 3 | Viewed by 908

Abstract

Spatial autocorrelation, which describes the similarity between signals on adjacent vertices, is central to spatial science, and Geary’s c is one of the most-prominent numerical measures of it. Using concepts from spectral graph theory, this paper documents new theoretical results on the measure. [...] Read more.

Spatial autocorrelation, which describes the similarity between signals on adjacent vertices, is central to spatial science, and Geary’s c is one of the most-prominent numerical measures of it. Using concepts from spectral graph theory, this paper documents new theoretical results on the measure. MATLAB/GNU Octave user-defined functions are also provided. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

23 pages, 6923 KiB

Open AccessArticle

Multi-View Learning-Based Fast Edge Embedding for Heterogeneous Graphs

by Canwei Liu, Xingye Deng, Tingqin He, Lei Chen, Guangyang Deng and Yuanyu Hu

Mathematics 2023, 11(13), 2974; https://doi.org/10.3390/math11132974 - 3 Jul 2023

Viewed by 1640

Abstract

Edge embedding is a technique for constructing low-dimensional feature vectors of edges in heterogeneous graphs, which are also called heterogeneous information networks (HINs). However, edge embedding research is still in its early stages, and few well-developed models exist. Moreover, existing models often learn [...] Read more.

Edge embedding is a technique for constructing low-dimensional feature vectors of edges in heterogeneous graphs, which are also called heterogeneous information networks (HINs). However, edge embedding research is still in its early stages, and few well-developed models exist. Moreover, existing models often learn features on the edge graph, which is much larger than the original network, resulting in slower speed and inaccurate performance. To address these issues, a multi-view learning-based fast edge embedding model is developed for HINs in this paper, called MVFEE. Based on the “divide and conquer” strategy, our model divides the global feature learning into multiple separate local intra-view features learning and inter-view features learning processes. More specifically, each vertex type in the edge graph (each edge type in HIN) is first treated as a view, and a private skip-gram model is used to rapidly learn the intra-view features. Then, a cross-view learning strategy is designed to further learn the inter-view features between two views. Finally, a multi-head attention mechanism is used to aggregate these local features to generate accurate global features of each edge. Extensive experiments on four datasets and three network analysis tasks show the advantages of our model. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

21 pages, 667 KiB

Open AccessArticle

The Square of Some Generalized Hamming Graphs

by Yipeng Li, Jing Zhang and Meili Wang

Mathematics 2023, 11(11), 2487; https://doi.org/10.3390/math11112487 - 28 May 2023

Viewed by 1282

Abstract

In this paper, we study the square of generalized Hamming graphs by the properties of abelian groups, and characterize some isomorphisms between the square of generalized Hamming graphs and the non-complete extended p-sum of complete graphs. As applications, we determine the eigenvalues [...] Read more.

In this paper, we study the square of generalized Hamming graphs by the properties of abelian groups, and characterize some isomorphisms between the square of generalized Hamming graphs and the non-complete extended p-sum of complete graphs. As applications, we determine the eigenvalues of the square of some generalized Hamming graphs. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

17 pages, 429 KiB

Open AccessArticle

Efficient and Effective Directed Minimum Spanning Tree Queries

by Zhuoran Wang, Dian Ouyang, Yikun Wang, Qi Liang and Zhuo Huang

Mathematics 2023, 11(9), 2200; https://doi.org/10.3390/math11092200 - 6 May 2023

Viewed by 2933

Abstract

Computing directed Minimum Spanning Tree (

D M S T

) is a fundamental problem in graph theory. It is applied in a wide spectrum of fields from computer network and communication protocol design to revenue maximization in social networks and syntactic parsing [...] Read more.

Computing directed Minimum Spanning Tree (

D M S T

) is a fundamental problem in graph theory. It is applied in a wide spectrum of fields from computer network and communication protocol design to revenue maximization in social networks and syntactic parsing in Natural Language Processing. State-of-the-art solutions are online algorithms that compute

D M S T

for a given graph and a root. For multi-query requirements, the online algorithm is inefficient. To overcome the drawbacks, in this paper, we propose an indexed approach that reuses the computation result to facilitate single and batch queries. We store all the potential edges of

D M S T

in a hierarchical tree in

O (n)

space complexity. Furthermore, we answer the

D M S T

query of any root in

O (n)

time complexity. Experimental results demonstrate that our approach can achieve a speedup of 2–3 orders of magnitude in query processing compared to the state-of-the-art while consuming O(n) index size. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

19 pages, 422 KiB

Open AccessArticle

Discrete Integral and Discrete Derivative on Graphs and Switch Problem of Trees

by M. H. Khalifeh and Abdol-Hossein Esfahanian

Mathematics 2023, 11(7), 1678; https://doi.org/10.3390/math11071678 - 31 Mar 2023

Viewed by 1424

Abstract

For a vertex and edge weighted (VEW) graph

G

with a vertex weight function

f_{G}

let [...] Read more.

For a vertex and edge weighted (VEW) graph

G

with a vertex weight function

f_{G}

let

W_{α, β} (G) = \sum_{{u, v} \subseteq V (G)} [α f_{G} (u) \times f_{G} (v) + β (f_{G} (u) + f_{G} (v))] d_{G} (u, v)

where,

α, β \in ℝ

and

d_{G} (u, v)

denotes the distance, the minimum sum of edge weights across all the paths connecting

u, v \in V (G)

. Assume

T

is a VEW tree, and

e \in E (T)

fails. If we reconnect the two components of

T - e

with new edge

ϵ \neq e

such that,

W_{α, β} (T_{ϵ \ e} = T - e + ϵ)

is minimum, then

ϵ

is called a best switch (BS) of

e

w.r.t.

W_{α, β}

. We define three notions: convexity, discrete derivative, and discrete integral for the VEW graphs. As an application of the notions, we solve some BS problems for positively VEW trees. For example, assume

T

is an

n

-vertex VEW tree. Then, for the inputs

e \in E (T)

and

w, α, β \in ℝ^{+}

, we return

ϵ

,

T_{ϵ \ e}

, and

W_{α, β} (T_{ϵ \ e})

with the worst average time of

O (\log n)

and the best time of

O (1)

where

ϵ

is a BS of

e

w.r.t.

W_{α, β}

and the weight of

ϵ

is

w

. Full article

(This article belongs to the Special Issue Advances in Graph Theory: Algorithms and Applications)

► Show Figures

Figure 1

Journal Menu

Journal Browser

Advances in Graph Theory: Algorithms and Applications

Share This Special Issue

Special Issue Editors

Special Issue Information

Keywords

Benefits of Publishing in a Special Issue

Published Papers (10 papers)

Research

Further Information

Guidelines

MDPI Initiatives

Follow MDPI