Search

The Graph Minors Structure Theorem of Robertson and Seymour asserts that, for every graph H, every H-minor-free graph can be obtained by clique-sums of "almost embeddable" graphs. Here a graph is "almost embeddable" if it can be obtained from a graph of bounded Euler-genus by pasting graphs of bounded pathwidth in an "orderly fashion" into a bounded number of faces, called the vortices, and then adding a bounded number of additional vertices, called apices, with arbitrary neighborhoods. Our main result is a full classification of all graphs H for which the use of vortices in the theorem above can be avoided. To this end, we identify a (parametric) graph \(\mathscr{S}_{t}\) and prove that all \(\mathscr{S}_{t}\) -minor-free graphs can be obtained by clique-sums of graphs embeddable in a surface of bounded Euler-genus after deleting a bounded number of vertices. We show that this result is tight in the sense that the appearance of vortices cannot be avoided for H-minor-free graphs, whenever H is not a minor of \(\mathscr{S}_{t}\) for some \(t\in \mathbb {N}\). Using our new structure theorem, we design an algorithm that, given an \(\mathscr{S}_{t}\) -minor-free graph G, computes the generating function of all perfect matchings of G in polynomial time. Our results, combined with known complexity results, imply a complete characterization of minor-closed graph classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every \(\mathscr{S}_{t}\) as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes. [ABSTRACT FROM AUTHOR]

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximalmatching either take polylogarithmic time which is considered inefficient, or require a strictly superlinear space of n1+Ω(1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [15]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition.We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O(log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O(log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds. [ABSTRACT FROM AUTHOR]

The restoration lemma by Afek et al. [3] proves that, in an undirected unweighted graph, any replacement shortest path avoiding a failing edge can be expressed as the concatenation of two original shortest paths. However, the lemma is tiebreaking-sensitive: if one selects a particular canonical shortest path for each node pair, it is no longer guaranteed that one can build replacement paths by concatenating two selected shortest paths. They left as an open problem whether a method of shortest path tiebreaking with this desirable property is generally possible. We settle this question affirmatively with the first general construction of restorable tiebreaking schemes. We then show applications to various problems in fault-tolerant network design. These include a faster algorithm for subset replacement paths, more efficient fault-tolerant (exact) distance labeling schemes, faulttolerant subset distance preservers and +4 additive spanners with improved sparsity, and fast distributed algorithms that construct these objects. For example, an almost immediate corollary of our restorable tiebreaking scheme is the first nontrivial distributed construction of sparse fault-tolerant distance preservers resilient to three faults. [ABSTRACT FROM AUTHOR]

In many scientific domains, there is a growing interest in the shortest path problem. Traffic routes that can be precisely defined become arbitrary due to the damage that natural catastrophes inflict on roads and bridges. The truth membership, indeterminacy membership, and falsity membership of the component elements make up a neutrosophic set. Their axis of symmetry is indeterminacy membership, and it has a symmetric form. The neutrosophic number is a better way to express the edge distance in uncertain circumstances. With an edge distance stated using Fermatean neutrosophic numbers (FrNN), the study aims to solve the shortest path problem of the Fermatean neutrosophic graph. Additionally, the edge distance will be resolved based on the score and precise functions derived from the FrNN. In order to solve the shortest path problem and determine the shortest distance, the application of a circle-breaking algorithm is suggested. [ABSTRACT FROM AUTHOR]

The deployment of increasingly diverse services on edge devices is becoming increasingly prevalent. Efficiently deploying functionally heterogeneous services to resource heterogeneous edge nodes while achieving superior user experience is a challenge that every edge system must address. In this paper, we propose a container-node graph (CN-Graph)-based container optimal matching deployment algorithm, edge Kuhn-Munkres algorithm (EKM) based on container-node graph, designed for heterogeneous environment to optimize system performance. Initially, containers are categorized by functional labels, followed by construction of a CN-Graph model based on the relationship between containers and nodes. Finally, the container deployment problem is transformed into a weighted bipartite graph optimal matching problem. In comparison with the mainstream container deployment algorithms, Swarm, Kubernetes, and the recently emerged ECSched-dp algorithm, the EKM algorithm demonstrates the ability to effectively enhance the average runtime performance of containers to 3.74 times, 4.10 times, and 2.39 times, respectively. [ABSTRACT FROM AUTHOR]

In the pursuit of graph processing performance, graph partitioning, as a crucial preprocessing step, has been widely concerned. Based on an in-depth analysis of Neighbor Expansion (NE) graph partitioning algorithm, we propose Parallel Expansion based on Clustering Coefficient (PECC). Firstly, to address the partition disturbance caused by internal structural changes during the process of vertex neighborhood expansion in the traditional NE algorithm, we perform a formal redefinition of the vertex state during the partitioning process and introduce the concept of clustering coefficient. Then, PECC uses the clustering coefficient as a metric to measure the closeness between vertices and potential partitions. Based on this metric, a novel parallel partitioning strategy in the distributed environment is proposed. This strategy consists of two core steps: the expansion process and the allocation process. Through two steps, PECC can effectively improve the operating efficiency of programs and significantly reduce the partitioning time. In addition, to ensure data consistency during parallel expansion, we adopt a distributed locking engine to solve concurrency management problems. Our evaluations on large real-world graphs show that in many cases, PECC achieves a balance between partitioning quality and computational efficiency. Finally, we show that PECC integrated on GraphX outperforms the built-in native algorithms. [ABSTRACT FROM AUTHOR]

Although graph convolutional networks have achieved good performances in skeleton‐graph‐based action recognition, there are still some problems which include the incomplete utilization of skeleton graph features and the lacking of logical adjacency information between nodes in adjacency matrix. In this article, a human action recognition algorithm is proposed based on multiple features from the skeleton graph to solve these problems. More specifically, an improved adjacency matrix is constructed to make full use of the multiple skeleton graph features. These features include local differential features, multi‐scale edge features, features of the original skeleton graph, nodal features, and nodal motion features. Extensive results are conducted on four standard datasets (NTU RGB‐D 60, NTU RGB‐D 120, Kinetics, and Northwestern‐UCLA). The experimental results show that the proposed algorithm outperforms the SOTA action recognition algorithms. [ABSTRACT FROM AUTHOR]

Efficiently mapping quantum circuits onto hardware is integral for the quantum compilation process, wherein a circuit is modified in accordance with a quantum processor's connectivity. Many techniques currently exist for solving this problem, wherein SWAP-gate overhead is usually prioritized as a cost metric. We reconstitute quantum circuit mapping using tools from quantum information theory, showing that a lower bound, which we dub the lightcone bound, emerges for a circuit executed on hardware. We also develop an initial placement algorithm based on graph similarity search, aiding us in optimally placing circuit qubits onto a device. 600 realistic benchmarks using the IBM Qiskit compiler and a brute-force method are then tested against the lightcone bound, with results unambiguously verifying the veracity of the bound, while permitting trustworthy estimations of minimal overhead in near-term realizations of quantum algorithms. This work constitutes the first use of quantum circuit uncomplexity to practically-relevant quantum computing. [ABSTRACT FROM AUTHOR]

This paper studies the security issues for cyber–physical systems, aimed at countering potential malicious cyber-attacks. The main focus is on solving the problem of extracting the most vulnerable attack path in a known attack graph, where an attack path is a sequence of steps that an attacker can take to compromise the underlying network. Determining an attacker's possible attack path is critical to cyber defenders as it helps identify threats, harden the network, and thwart attacker's intentions. We formulate this problem as a path-finding optimization problem with logical constraints represented by AND and OR nodes. We propose a new Dijkstra-type algorithm that combines elements from Dijkstra's shortest path algorithm and the critical path method. Although the path extraction problem is generally NP-hard, for the studied special case, the proposed algorithm determines the optimal attack path in polynomial time, O (n m) , where n is the number of nodes and m is the number of edges in the attack graph. To our knowledge this is the first exact polynomial algorithm that can solve the path extraction problem for different attack graphs, both cycle-containing and cycle-free. Computational experiments with real and synthetic data have shown that the proposed algorithm consistently and quickly finds optimal solutions to the problem. [ABSTRACT FROM AUTHOR]

It is well known that networks are dynamic graphs, and the topology of a network can be described by a graph. Thus, the reliability of a network under edge failure is defined as the probability that its corresponding topological graph remains connected under the condition that the edges fail with independent probabilities. In this paper, the reliability of a class of two-layer networks is considered, where each layer is a complete graph and the edges joining different layers are one-to-one correspondingly connected. The edge failure probability is uniform in the same layer and distinct in different layers and between layers. The recursive formula for the reliability (reliability polynomial) of the two-layer network is obtained, and the corresponding algorithm is also given. Furthermore, the reliability of several networks is computed by Python, which verifies the correctness of the algorithm. [ABSTRACT FROM AUTHOR]

The instability of solar energy is the biggest challenge to its successful integration with modern power grids, and accurate prediction of long‐term solar radiation can effectively solve this problem. In this study, we proposed a novel long‐term solar radiation prediction model based on time series imaging and bidirectional long short‐term memory network. First, inspired by the computer vision algorithm, the recursive graph algorithm is used to transform the one‐dimensional time series into two‐dimensional images, and then convolutional neural network is used to extract the features from the images, thus, the deeper features in the original solar radiation data can be mined. Second, to solve the problem of low accuracy of long‐term solar radiation prediction, a hybrid model BiLSTM‐Transformer is used to predict long‐term solar radiation. The hybrid prediction model can capture the long‐term dependencies, thereby further improving the accuracy of the prediction model. The experimental results show that the hybrid model proposed in this study is superior to other single models and hybrid models in long‐term solar radiation prediction accuracy. The accuracy and stability of the hybrid model are verified by many tests. [ABSTRACT FROM AUTHOR]

We present a method based on graph community detection algorithms to analyse velocity fields induced by an intruder particle impinging upon a stationary bed of particles. Based on velocity relations between the pairs of adjacent particles, the “velocity similarity” graphs are built where the graph vertices represent the particles and the edge weights are calculated according to the velocities of the respective particle pairs. A few different expressions for the edge weights are tested. Based on the graph, a Louvain community detection algorithm with the “geographic” null model is used to identify the groups of particles moving in a coordinated manner, represented in the graph as a community of vertices, for which the community detection algorithms developed for graph analysis can be applied. Selection of the expression of the graph edge weights based on the velocities of the respective particles influences the resulting graph structure and thereby has an influence on the community detection results. [ABSTRACT FROM AUTHOR]

This paper introduces Tensor Visibility Graph-enhanced Attention Networks (TVGeAN), a novel graph autoencoder model specifically designed for MTS learning tasks. The underlying approach of TVGeAN is to combine the power of complex networks in representing time series as graphs with the strengths of Graph Neural Networks (GNNs) in learning from graph data. TVGeAN consists of two new main components: TVG which extend the capabilities of visibility graph algorithms in representing MTSs by converting them into weighted temporal graphs where both the nodes and the edges are tensors. Each node in the TVG represents the MTS observations at a particular time, while the weights of the edges are defined based on the visibility angle algorithm. The second main component of the proposed model is GeAN, a novel graph attention mechanism developed to seamlessly integrate the temporal interactions represented in the nodes and edges of the graphs into the core learning process. GeAN achieves this by using the outer product to quantify the pairwise interactions of nodes and edges at a fine-grained level and a bilinear model to effectively distil the knowledge interwoven in these representations. From an architectural point of view, TVGeAN builds on the autoencoder approach complemented by sparse and variational learning units. The sparse learning unit is used to promote inductive learning in TVGeAN, and the variational learning unit is used to endow TVGeAN with generative capabilities. The performance of the TVGeAN model is extensively evaluated against four widely cited MTS benchmarks for both supervised and unsupervised learning tasks. The results of these evaluations show the high performance of TVGeAN for various MTS learning tasks. In particular, TVGeAN can achieve an average root mean square error of 6.8 for the C-MPASS dataset (i.e., regression learning tasks) and a precision close to one for the SMD, MSL, and SMAP datasets (i.e., anomaly detection learning tasks), which are better results than most published works. [ABSTRACT FROM AUTHOR]

Deploying the Internet of Things (IoT) in integrated edge‐cloud environments exposes the IoT traffic data to performance issues such as delay, bandwidth limitation etc. Recently, Software‐Defined Wide Area Network (SD‐WAN) has emerged as an architecture that originates from the Software‐Defined Network (SDN) paradigm and provides solutions for networking multiple data centers by allowing network administrators to manage and control network layers. In this article, an SDWAN‐based policy for traffic management in IoT is introduced in which the Quality of Service (QoS) metrics such as end‐to‐end delay and bandwidth utilization are optimized. The proposed method implements the traffic management policy in the SDWAN controller. When the IoT traffic flows reach the SDWAN infrastructure network, graph search algorithms are performed to find the near‐optimal paths that affect the end‐to‐end delay of traffic flows. Because of the ability of deep learning to process complex data, a deep RNN model is used to predict the network state information, such as link latency and available bandwidth, before the traffic flows reach the infrastructure network. The proposed method consists of four key modules to predict the routes for future time intervals: (a) an SD‐WAN topology updater unit that checks the link changes and availability, (b) the network state information collector, which collects the network state information to create a dataset, (c) the learning unit, which trains a deep RNN model using the created dataset, and (d) the route predictor unit, which uses the trained model to predict the network state information using a heuristic algorithm to determine the routes. The simulation results showed that the deep RNN model can achieve high accuracy and low Mean Absolute Error (MAE), and the proposed method outperforms shortest‐path algorithms in terms of latency. At the same time, the available bandwidth is almost fairly distributed among all network links. [ABSTRACT FROM AUTHOR]

Precipitation channelled down tree stems (stemflow) or into drip points of 'throughfall' beneath trees results in spatially concentrated inputs of water and chemicals to the ground. Currently, these flows are poorly characterised due to uncertainties about which branches redirect rainfall to stemflow or throughfall drip points.We introduce a graph theoretic algorithm that 'prunes' quantitative structural models of trees (derived from terrestrial LiDAR) to identify branches contributing to stemflow and those contributing to throughfall drip points. To demonstrate the method's utility, we analysed two trees with similar canopy sizes but contrasting canopy architecture and rainfall partitioning behaviours.For both trees, the branch 'watershed' area contributing to stemflow (under conditions assumed to represent moderate precipitation intensity) was found to be only half of the total ground area covered by the canopy. The study also revealed significant variations between trees in the number and median contribution areas of modelled throughfall drip points (69 vs. 94 drip points tree−1, with contributing projected areas of 28.6 vs. 7.8 m2 tree−1, respectively). Branch diameter, surface area, volumes and woody area index of components contributing to stemflow and throughfall drip points may play a role in the trees' differing rainfall partitioning behaviours.Our pruning algorithm, enabled by the proliferation of LiDAR observations of canopy structure, promises to enhance studies of canopy hydrology. It offers a novel approach to refine our understanding of how trees interact with rainfall, thereby broadening the utility of existing LiDAR data in environmental research. [ABSTRACT FROM AUTHOR]

Transposable elements are ubiquitous mobile DNA sequences generating insertion polymorphisms, contributing to genomic diversity. We present GraffiTE, a flexible pipeline to analyze polymorphic mobile elements insertions. By integrating state-of-the-art structural variant detection algorithms and graph genomes, GraffiTE identifies polymorphic mobile elements from genomic assemblies or long-read sequencing data, and genotypes these variants using short or long read sets. Benchmarking on simulated and real datasets reports high precision and recall rates. GraffiTE is designed to allow non-expert users to perform comprehensive analyses, including in models with limited transposable element knowledge and is compatible with various sequencing technologies. Here, we demonstrate the versatility of GraffiTE by analyzing human, Drosophila melanogaster, maize, and Cannabis sativa pangenome data. These analyses reveal the landscapes of polymorphic mobile elements and their frequency variations across individuals, strains, and cultivars. Transposable element (TE) activity affects genome structure. Here, authors present GraffiTE, a framework for analysing polymorphic TEs in long reads or assemblies. It combines state-of-the-art variant search, TE annotation, and graph-genotyping, and has proven versatile across eukaryotic models. [ABSTRACT FROM AUTHOR]

Let G(p,q) be a simple graph, where p is the number of vertices and q is the number of edges if there exists a one-to-one mapping f: E(G)→{1,2,...,|E|}, so that for any two vertices uv∈E(G), if d(u)=d(v), then S(u)=S(v), where ... represents the degree of vertex u, f is called the Adjacent Vertex Reducible Edge Labeling (AVREL) of G. Building on the current graph labeling algorithm, a heuristic search algorithm is designed, and this algorithm is used to label random graphs with less than 12 vertices and obtain the result set of adjacent vertex reducible edge labeling. Based on the analysis of the result set and combining it with the known theorem, the adjacent vertex reducible edge labeling law of other compound graphs is obtained, and the related proof is given. [ABSTRACT FROM AUTHOR]

In agricultural field inspection robots, constructing accurate environmental maps and achieving precise localization are essential for effective Light Detection And Ranging (LiDAR) Simultaneous Localization And Mapping (SLAM) navigation. However, navigating in occluded environments, such as mapping distortion and substantial cumulative errors, presents challenges. Although current filter-based algorithms and graph optimization-based algorithms are exceptionally outstanding, they exhibit a high degree of complexity. This paper aims to investigate precise mapping and localization methods for robots, facilitating accurate LiDAR SLAM navigation in agricultural environments characterized by occlusions. Initially, a LiDAR SLAM point cloud mapping scheme is proposed based on the LiDAR Odometry And Mapping (LOAM) framework, tailored to the operational requirements of the robot. Then, the GNU Image Manipulation Program (GIMP) is employed for map optimization. This approach simplifies the map optimization process for autonomous navigation systems and aids in converting the Costmap. Finally, the Adaptive Monte Carlo Localization (AMCL) method is implemented for the robot's positioning, using sensor data from the robot. Experimental results highlight that during outdoor navigation tests, when the robot operates at a speed of 1.6 m/s, the average error between the mapped values and actual measurements is 0.205 m. The results demonstrate that our method effectively prevents navigation mapping distortion and facilitates reliable robot positioning in experimental settings. [ABSTRACT FROM AUTHOR]

This paper presents three novel encryption and decryption schemes based on graph theory that aim to improve security and error resistance in communication networks. The novelty of this work lies in the application of complete bipartite graphs in two of the schemes and the Cartesian product of graphs in the third, representing a unique approach to cryptographic algorithm development. Unlike traditional cryptographic methods, these graph-based schemes use structural properties of graphs to achieve robust encryption, providing greater resistance to attacks and corruption. Each scheme is illustrated with detailed examples that show how the algorithms can be successfully implemented. The algorithms are written in standard mathematical notation, making them adaptable for machine implementation and scalable for real-world use. The schemes are also rigorously analyzed and compared in terms of their temporal and spatial complexities, using Big O notation. This comprehensive evaluation focuses on their effectiveness, providing valuable insights into their potential for secure communication in modern networks. [ABSTRACT FROM AUTHOR]

The logistics demands of industries represented by e-commerce have experienced explosive growth in recent years. Vehicle path-planning plays a crucial role in optimization systems for logistics and distribution. A path-planning scheme suitable for an actual scenario is the key to reducing costs and improving service efficiency in logistics industries. In complex application scenarios, however, it is difficult for conventional heuristic algorithms to ensure the quality of solutions for vehicle routing problems. This study proposes a joint approach based on the genetic algorithm and graph convolutional network for solving the capacitated vehicle routing problem with multiple distribution centers. First, we use the heuristic method to modularize the complex environment and encode each module based on the constraint conditions. Next, the graph convolutional network is adopted for feature embedding for the graph representation of the vehicle routing problem, and multiple decoders are used to increase the diversity of the solution space. Meanwhile, the REINFORCE algorithm with a baseline is employed to train the model, ensuring quick returns of high-quality solutions. Moreover, the fitness function is calculated based on the solution to each module, and the genetic algorithm is employed to seek the optimal solution on a global scale. Finally, the effectiveness of the proposed framework is validated through experiments at different scales and comparisons with other algorithms. The experimental results show that, compared to the single decoder GCN-based solving method, the method proposed in this paper improves the solving success rate to 100% across 15 generated instances. The average path length obtained is only 11% of the optimal solution produced by the GCN-based multi-decoder method. [ABSTRACT FROM AUTHOR]

Graph pattern matching is widely used in real-world applications, such as social network analysis. Since the traditional subgraph isomorphism is NP-complete and often too restrictive to catch sensible matches, relaxed graph pattern matching models are used. However, existing algorithms suffer from limited linear scalability and restricted degrees of parallelism. In this paper, we propose fast parallel algorithms, GPGS and GPDS, for graph simulation and dual simulation, respectively. They make most use of the GPU performance by adopting the edge-centric processing model. We perform parallel computations on the data graph edges to evaluate the matching constraints for each vertex allowing for fast and scalable algorithms. To the best of our knowledge, we present the first GPU-based algorithms for graph simulation and dual simulation. Extensive experiments on synthetic and real-world data graphs demonstrate that our algorithms significantly outperform existing methods, achieving up to 74.8 × acceleration for GPGS and up to 114.2 × acceleration for GPDS. [ABSTRACT FROM AUTHOR]

Entanglement is crucial for achieving quantum advantages. However, in the context of quantum machine learning, existing optimization strategies for generating quantum classifier circuits often result in unentangled circuits, indicating an underutilization of the entanglement effect needed to learn complex patterns. In this study, we proposed a novel metaheuristic approach—genetic algorithm—for designing a quantum kernel classifier that incorporates expressive entanglement. This classifier utilizes a loopless entanglement‐directed graph, where each directed edge represents the entanglement between the target and control qubits. The proposed method consistently outperforms classical and quantum baselines across various artificial and actual datasets, achieving improvements up to 32.4% and 17.5%, respectively, compared with the best model among all other baselines. Moreover, this method successfully reconstructs the hidden entanglement structures underlying artificial datasets. The results also demonstrate that the optimized circuits exhibit diverse entanglement variations across different datasets, indicating the versatility of the proposed approach. [ABSTRACT FROM AUTHOR]

A satisfactory partition is a partition of undirected-graph vertices such that the partition has only two nonempty parts, and every vertex has at least as many adjacent vertices in its part as it has in the other part. Generally, the problem of determining whether a given undirected graph has a satisfactory partition is known to be NP-complete. In this paper, we show that for a given undirected graph with n vertices, a satisfactory partition (if any exists) can be computed recursively with a recursion tree of depth of O (ln ⁡ n) in expectation. Subsequently, we show that a satisfactory partition for those undirected graphs with recursion tree depth meeting the expectation can be computed in time O (n 3 2 O (ln ⁡ n)). [ABSTRACT FROM AUTHOR]

In this paper, we introduce the zero-divisor associate graph ΓD(R) over a finite commutative ring R. It is a simple undirected graph whose vertex set consists of all non-zero elements of R, and two vertices a, b are adjacent if and only if there exist non-zero zero-divisors z1, z2 in R such that az1 = bz2. We determine the necessary and sufficient conditions for connectedness and completeness of ΓD(R) for a unitary commutative ring R. The chromatic number of ΓD(R) is also studied. Next, we characterize the rings R for which ΓD(R) becomes a line graph of some graph. Finally, we give the complete list of graphs with at most 15 vertices which are realizable as ΓD(R), characterizing the associated ring R in each case. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph with diameter d, and k ∈ [1, d] be an integer. A radio k-coloring of graph G is a mapping g : V(G) → {0} ∪ N satisfying |g(u) - g(v)| ≥ 1 + k - d(u, v) for any pair of distinct vertices u and v of the graph G, where d(u, v) denotes distance between vertices u and v in G. The number max{g(u) : u ∈ V(G)} is known as the span of g and is denoted by rck(g). The radio k-chromatic number of graph G, denoted by rck(G), is defined as min{rck(g) : g is a radio k-coloring of G}. For k = d-1, the radio k-coloring of graph G is called an antipodal coloring. So rcd-1(G) is called the antipodal number of G and is denoted by ac(G). Here, we study antipodal coloring of the Cartesian product of the complete graph Kr and cycle Cs, Kr...Cs, for r ≥ 4 and s ≥ 3. We determine the antipodal number of Kr...Cs, for even r ≥ 4 with s ≡ 1 (mod 4); and for any r ≥ 4 with s = 4t + 2, t odd. Also, for the remaining values of r and s, we give lower and upper bounds for ac(Kr...Cs). [ABSTRACT FROM AUTHOR]

The folded hypercube FQn is the Cayley graph Cay(Z2n, S), where S = {e1, e2, ..., en} ∪ {u = e1 + e2 + ... + en}, and ei = (0, ..., 0, 1, 0, ..., 0), with 1 at the ith position, 1 ≤ i ≤ n. In this paper, we show that the folded hypercube FQn is a distance-transitive graph. Then, we study some properties of this graph. In particular, we show that if n ≥ 4 is an even integer, then the folded hypercube FQn is an automorphic graph, that is, FQn is a distance-transitive primitive graph which is not a complete or a line graph. [ABSTRACT FROM AUTHOR]

Let R be a finite commutative ring with or without unity and Γe(R) be its extended zero-divisor graph with vertex set Z*(R) = Z(R)\{0} and two distinct vertices x, y are adjacent if and only if x.y = 0 or x + y ∈ Z*(R). In this paper, we characterize finite commutative rings whose extended zero-divisor graph have clique number 1 or 2. We completely characterize the rings of the form R ≅ R1 x R2, where R1 and R2 are local, having clique number 3, 4 or 5. Further we determine the rings of the form R ≅ R1 x R2 x R3, where R1, R2 and R3 are local rings, to have clique number equal to six. [ABSTRACT FROM AUTHOR]

Let r ≥ 2. A subset S of vertices of a graph G is a r-hop independent dominating set if every vertex outside S is at distance r from a vertex of S, and for any pair v, w ∈ S, d(v, w) ≠ r. A r-hop Roman dominating function (rHRDF) is a function f on V (G) with values 0, 1 and 2 having the property that for every vertex v ∈ V with f(v) = 0 there is a vertex u with f(u) = 2 and d(u, v) = r. A r-step Roman dominating function (rSRDF) is a function f on V (G) with values 0, 1 and 2 having the property that for every vertex v with f(v) = 0 or 2, there is a vertex u with f(u) = 2 and d(u, v) = r. A rHRDF f is a r-hop Roman independent dominating function if for any pair v, w with non-zero labels under f, d(v, w) ≠ r. We show that the decision problem associated with each of r-hop independent domination, r-hop Roman domination, r-hop Roman independent domination and r-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs. [ABSTRACT FROM AUTHOR]

In this article, we discussed the zero-divisor graph of a commutative ring with identity Fp + uFp + u²Fp where u³ = 0 and p is an odd prime. We find the clique number, chromatic number, vertex connectivity, edge connectivity, diameter and girth of a zero-divisor graph associated with the ring. We find some of topological indices and the main parameters of the code derived from the incidence matrix of the zero-divisor graph Γ(R). Also, we find the eigenvalues, energy and spectral radius of both adjacency and Laplacian matrices of Γ(R). [ABSTRACT FROM AUTHOR]

The commuting graph of a finite non-commutative semigroup S, denoted by Δ(S), is the simple graph whose vertices are the non-central elements of S and two distinct vertices x, y are adjacent if xy = yx. In this paper, we study the commuting graph of an important class of inverse semigroups viz. Brandt semigroup Bn. In this connection, we obtain the automorphism group Aut(Δ(Bn)) and the endomorphism monoid End(Δ(Bn)) of Δ(Bn). We show that Aut(Δ(Bn)) ≅ Sn x Z2, where Sn is the symmetric group of degree n and Z2 is the additive group of integers modulo 2. Further, for n ≥ 4, we prove that End(Δ(Bn)) = Aut(Δ(Bn)). Moreover, we provide the vertex connectivity and edge connectivity of Δ(Bn). This paper provides a partial answer to a question posed in [3] and so we ascertained a class of inverse semigroups whose commuting graph is Hamiltonian. [ABSTRACT FROM AUTHOR]

A subset S of vertices of a graph G is in general position if no shortest path in G contains three vertices of S. The general position problem consists of finding the number of vertices in a largest general position set of G, whilst the lower general position problem asks for a smallest maximal general position set. In this paper we determine the lower general position numbers of several families of Cartesian products. We also show that the existence of small maximal general position sets in a Cartesian product is connected to a special type of general position set in the factors, which we call a terminal set, for which adding any vertex u from outside the set creates three vertices in a line with u as an endpoint. We give a constructive proof of the existence of terminal sets for graphs with diameter at most three. We also present conjectures on the existence of terminal sets for all graphs and a lower bound on the lower general position number of a Cartesian product in terms of the lower general position numbers of its factors. [ABSTRACT FROM AUTHOR]

An edge e of a simple graph G = (VG, EG) is said to ev-dominate a vertex v ∈ VG if e is incident with v or e is incident with a vertex adjacent to v. A subset D ⊆ EG is an edge-vertex dominating set (or an evd-set for short) of G if every vertex of G is ev-dominated by an edge of D. The edge-vertex domination number of G is the minimum cardinality of an evd-set of G. In this paper, we initiate the study of the graphs with unique minimum evd-sets that we will call UEVD-graphs. We first present some basic properties of UEVD-graphs, and then we characterize UEVD-trees by equivalent conditions as well as by a constructive method. [ABSTRACT FROM AUTHOR]

For n ≥ 2t + 1 where t ≥ 1, the circulant graph Cn(1, 2, ..., t) consists of the vertices v0, v1, v2, ..., vn-1 and the edges vivi+1, vivi+2, ..., vivi+t, where i = 0, 1, 2, ..., n-1, and the subscripts are taken modulo n. We prove that the metric dimension dim(Cn(1, 2, ..., t)) ≥ ... + 1 for t ≥ 5, where the equality holds if and only if t = 5 and n = 13. Thus dim(Cn(1, 2, ..., t)) ≥ ... + 2 for t ≥ 6. This bound is sharp for every t ≥ 6. [ABSTRACT FROM AUTHOR]

A vertex u of a graph G = (V, E) ve-dominates every edge incident to u as well as every edge adjacent to these incident edges. A set S ⊆ V is a vertex-edge dominating set (or a ved-set for short) if every edge of E is ve-dominated by at least one vertex in S. A ved-set is independent if its vertices are pairwise non-adjacent. The independent ve-domination number ive(G) is the minimum cardinality of an independent ved-set and the upper independent ve-domination number βve(G) is the maximum cardinality of a minimal independent ved-set of G. In this paper, we are interesting in graphs G such that ive(G) = βve(G), which we call well ve-covered graphs. We show that recognizing well ve-covered graphs is co-NP-complete, and we present a constructive characterization of well ve-covered trees. [ABSTRACT FROM AUTHOR]

The complement of the intersection graph of subgroups of a group G, denoted by Ic(G), is the graph whose vertex set is the set of all nontrivial proper subgroups of G and its two distinct vertices H and K are adjacent if and only if H ∩ K = 1, where 1 denotes the trivial subgroup of G. In this paper, we classify all finite groups whose complement of the intersection graph of subgroups is one of totally disconnected, bipartite, complete bipartite, tree, star graph or C3-free. Also we characterize all the finite groups whose complement of the intersection graph of subgroups is planar. [ABSTRACT FROM AUTHOR]

In 2020, mathematical chemist, Ivan Gutman, introduced a new vertex-degree-based topological index called the Sombor Index, denoted by SO (G), where G is a simple, connected, finite, graph. This paper aims to present some novel formulas, along with some upper and lower bounds on the Sombor Index of generalized Sierpiński graphs; originally defined by Klavžar and Milutinović by replacing the complete graph appearing in S (n, k) with any graph and exactly replicating the same graph, yielding self-similar graphs of fractal nature; and on the Sombor Index of the m-Mycielskian or the generalized Mycielski graph; formed from an interesting construction given by Jan Mycielski (1955); of some simple graphs such as Kn, Cn², Cn, and Pn. We also provide Python codes to verify the results for the SO (S (n, Km)) and SO (μm (Kn)). [ABSTRACT FROM AUTHOR]

For any graph, Weisfeiler and Leman assigned the smallest matrix algebra which contains the adjacency matrix of the graph. The coherent configuration underlying this algebra for a graph Γ is called the coherent configuration of Γ, denoted by X(Γ). In this paper, we study the coherent configuration of circular-arc graphs. We give a characterization of the circular-arc graphs Γ, where X(Γ) is a homogeneous coherent configuration. Moreover, all homogeneous coherent configurations which are obtained in this way are characterized as a subclass of Schurian coherent configurations. [ABSTRACT FROM AUTHOR]

In this article, we discussed the zero-divisor graph of a commutative ring with identity Fp + uFp + u²Fp where u³ = 0 and p is an odd prime. We find the clique number, chromatic number, vertex connectivity, edge connectivity, diameter and girth of a zero-divisor graph associated with the ring. We find some of topological indices and the main parameters of the code derived from the incidence matrix of the zero-divisor graph Γ(R). Also, we find the eigenvalues, energy and spectral radius of both adjacency and Laplacian matrices of Γ(R). [ABSTRACT FROM AUTHOR]

The Vertex Graph Coloring problem (VGC ) is a well-known difficult combinatorial optimization problem. It is one of Karp's 21 NP-complete problems. It consists in assigning a color to each vertex of a graph in such a way that any two neighboring vertices do not share the same color, and the number of the used colors is minimized. VGC is used to solve a variety of real-world problems such as time tabling and scheduling, radio frequency assignment, and computer register allocation. To deal with this problem on large graphs, the emerging large graph processing frameworks are an excellent promising candidate. Giraph is one of the most popular large graph processing frameworks both in industry and academia. In this work, two novel graph coloring algorithms are introduced. These algorithms designed to reap the benefit of the simple parallelization model offered by any vertex-centric frameworks, such as Giraph. The algorithms are based on well-known sequential heuristic techniques namely Largest-First (LF) and Saturation Largest-First (SLF). We have compared the performances of the proposed algorithms to previous Giraph based graph coloring algorithms, with regard to their solution quality and executing time, using benchmark graphs from the SNAP library. The obtained experimental results have revealed that the proposed algorithms are much more efficient than the existing Giraph algorithms. [ABSTRACT FROM AUTHOR]

Network security policy is regarded as a guideline for the use and management of the network environment, which usually formulates various requirements in the form of natural language. It can help network managers conduct standardized network attack detection and situation awareness analysis in the overall time and space environment of network security. However, in most cases, due to configuration updates or policy conflicts, there are often differences between the real network environment and network security policies. In this case, the consistency detection of network security policies is necessary. The previous consistency detection methods of security policies have some problems. Firstly, the detection direction is single, only focusing on formal reasoning methods to achieve logical consistency detection and solve problems. Secondly, the detection policy field is not comprehensive, focusing only on a certain type of problem in a certain field. Thirdly, there are numerous forms of data structures used for consistency detection, and it is difficult to unify the structured processing and analysis of rule library carriers and target information carriers. With the development of intelligent graph and data mining technology, the above problems have the possibility of optimization. This article proposes a new consistency detection approach for network security policy, which uses an intelligent graph database as a visual information carrier, which can widely connect detection information and achieve comprehensive detection across knowledge domains, physical devices, and detection methods. At the same time, it can also help users grasp the security associations with the real network environment based on the graph algorithm of the knowledge graph and intelligent reasoning. Furthermore, these actual network situations and knowledge bases can help managers improve policies more tailored to local conditions. This article also introduces the consistency detection process of typical cases of network security policies, demonstrating the practical details and effectiveness of this method. [ABSTRACT FROM AUTHOR]

In complex urban road environments, vehicles inevitably experience frequent or sustained interruptions of the Global Navigation Satellite System (GNSS) signal when passing through overpasses, near tall buildings, and through tunnels. This results in the reduced accuracy and robustness of the GNSS/Inertial Navigation System (INS) integrated navigation systems. To improve the performance of GNSS and INS integrated navigation systems in complex environments, particularly during GNSS outages, we propose a convolutional neural network–gated recurrent unit (CNN-GRU)-assisted factor graph hybrid navigation method. This method effectively combines the spatial feature extraction capability of CNN, the temporal dynamic processing capability of GRU, and the data fusion strength of a factor graph, thereby better addressing the impact of GNSS outages on GNSS/INS integrated navigation. When GNSS signals are strong, the factor graph algorithm integrates GNSS/INS navigation information and trains the CNN-GRU assisted prediction model using INS velocity, acceleration, angular velocity, and GNSS position increment data. During GNSS outages, the trained CNN-GRU assisted prediction model forecasts pseudo GNSS observations, which are then integrated with INS calculations to achieve integrated navigation. To validate the performance and effectiveness of the proposed method, we conducted real road tests in environments with frequent and sustained GNSS interruptions. Experimental results demonstrate that the proposed method provides higher accuracy and continuous navigation outcomes in environments with frequent and sustained GNSS interruptions, compared to traditional GNSS/INS factor graph integrated navigation methods and long short-term memory (LSTM)-assisted GNSS/INS factor graph navigation methods. [ABSTRACT FROM AUTHOR]

An algorithm is described to find the shortest route through a field of obstacles of arbitrary shapes and positions. It has the appreciable advantage of not having to find mathematical formulas to represent the obstacles: it works directly with a digital image of the terrain and is implemented solely with standard graphical functions. Key to this algorithm is the definition of digraphs, the edges of which are built with obstacle bitangents and border enveloping convex arcs that incorporate the fundamental features of shortest paths. These graphs have a remarkably lower cardinality than those that have been proposed before to solve this problem; their edges are a concatenation of sequences of what individual edges and nodes are in formerly defined graphs. Furthermore, a thorough analysis of the topology of the terrain yields a procedure to eliminate the edges that have no possibility of being part of the shortest path. The A* graph optimization algorithm is adapted to deal with this type of graph. A new quite general theorem is proved, which applies to all graphs in which the triangle inequality holds, which allows the discarding of one of the normal steps of the A* algorithm. The effectiveness of the algorithm is demonstrated by calculating the shortest path for real complex terrains of areas between 25 km2 and 900 km2. In all cases, the required calculation time is less than 0.6 s on a Core i7-10750H CPU @ 2.60 GHz laptop computer. [ABSTRACT FROM AUTHOR]

Multi-tote storage and retrieval (MTSR) autonomous mobile robots can carry multiple product totes, store and retrieve them from different shelf rack tiers, and transport them to a workstation where the products are picked to fulfill customer orders. In each robot trip, totes retrieved during the previous trip must be stored. This leads to a mixed storage and retrieval route. We analyze this mixed storage and retrieval route problem and derive the optimal travel route for a multiblock warehouse by a layered graph algorithm, based on storage first-retrieval second and mixed storage and retrieval policies. We also propose an effective heuristic routing policy, the closest retrieval (CR) sequence policy, based on a local shortest path. Numerical results show that the CR policy leads to shorter travel times than the well-known S-shape policy, whereas the gap with the optimal mixed storage and retrieval policy in practical scenarios is small. Based on the CR policy, we model the stochastic behavior of the system using a semiopen queuing network (SOQN). This model can accurately estimate average tote throughput time and system throughput capacity as a function of the number of robots in the system. We use the SOQN and corresponding closed queuing network models to optimize the total annual cost as a function of the warehouse shape, the number of robots, and tote buffer positions on the robots for a given average tote throughput time and throughput capacity. Compared with robots that retrieve a single tote per trip, an MTSR system with at least five buffer positions can achieve lower operational costs while meeting given average tote throughput time and tote throughput capacity constraints. Funding: This work was supported by National Natural Science Foundation of China [Grant 72372088] and the Shenzhen Science and Technology Program [Grant GJHZ20220913143003006]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2023.0397. [ABSTRACT FROM AUTHOR]

In urban road environments, global navigation satellite system (GNSS) signals may be interrupted due to occlusion by buildings and obstacles, resulting in reduced accuracy and discontinuity of combined GNSS/inertial navigation system (INS) positioning. Improving the accuracy and robustness of combined GNSS/INS positioning systems for land vehicles in the presence of GNSS interruptions is a challenging task. The main objective of this paper is to develop a method for predicting GNSS information during GNSS outages based on a long short-term memory (LSTM) neural network to assist in factor graph-based combined GNSS/INS localization, which can provide a reliable combined localization solution during GNSS signal outages. In an environment with good GNSS signals, a factor graph fusion algorithm is used for data fusion of the combined positioning system, and an LSTM neural network prediction model is trained, and model parameters are determined using the INS velocity, inertial measurement unit (IMU) output, and GNSS position incremental data. In an environment with interrupted GNSS signals, the LSTM model is used to predict the GNSS positional increments and generate the pseudo-GNSS information and the solved results of INS for combined localization. In order to verify the performance and effectiveness of the proposed method, we conducted real-world road test experiments on land vehicles installed with GNSS receivers and inertial sensors. The experimental results show that, compared with the traditional combined GNSS/INS factor graph localization method, the proposed method can provide more accurate and robust localization results even in environments with frequent GNSS signal loss. [ABSTRACT FROM AUTHOR]

This paper presents an edge‐based event‐triggered delay distributed algorithm for solving the economic dispatch problem (EDP) in smart grids. The objective of the EDP is to minimize the total generation cost by allocating power to individual generators, each with its local generation constraint. To save the overhead of communication resources between agents, an edge‐based event‐triggered mechanism is suggested. By setting distinct triggering thresholds for each communication edge, the agent may efficiently regulate the communication frequency among all neighbors. However, in practice, owing to the instability of the network, the agent may receive information regarding its neighbors, leading to communication lags for every communication link. The virtual agent technique and double‐stochastic matrix augmentation technique provide an equivalent delay‐free EDP. It is demonstrated that the proposed algorithm can asymptotically converge to the global optimal solution as long as the communication delay is arbitrary, time‐varying, and random, but bounded. Objective and clear evidence is provided through a case study in smart grids to verify the algorithm's feasibility. [ABSTRACT FROM AUTHOR]

The existing signed graph neural networks mainly focus on the design process of neighbor aggregation function, but ignore the correlation between nodes, which leads to the decline of the representation ability of neural networks. In order to solve the above problems, a SDEGNN (Signed Distance Encoding based on Graph Neural Network) model based on enhanced signed distance encoding is proposed in this paper. Firstly, the problem of limited representation ability in signed graph neural networks is discussed. Secondly, in order to capture the correlation between nodes, signed distance encoding is proposed as the node feature representation to enhance the representation ability of the model. Thirdly, the signed distance encoding is injected into the information aggregation process of the signed graph convolutional network, and the objective function is proposed to optimize the SDEGNN model. The SDEGNN model is verified performance by three real signed network datasets Bitcoin-OTC, Bitcoin-Alpha, and Wiki-RfA. The experimental results show that the SDEGNN model can effectively improve the accuracy of link sign prediction tasks. [ABSTRACT FROM AUTHOR]

To solve some scheduling problems of batch processes based on timed Petri net models, timed extended reachability graphs (TERGs) and approximated TERGs can be used. Such graphs abstract temporal specifications and represent parts of timed languages. By exploring the feasible trajectories in a TERG, optimal schedules can be obtained with respect to the makespans of batch processes that are modeled by timed Petri nets. Nevertheless, the rapid growth of the number of states in a TERG makes the problem intractable for large systems. In this paper, we improve the existing clustering TERG approach, and we make it suitable for large sized batch processes. We also enlarge a systematic approach to model batch processes with timed Petri nets. Finally, a comprehensive example of scheduling problem is studied for an archetypal chemical production plant in order to illustrate the efficiency of the proposed approach. • The scheduling issue of batch chemical processes is formalized with timed Petri nets. • A graph named ClusTERG approximates the state space through hierarchical clustering. • The approximation error of this ClusTERG is far less than other approximations. • Such an approach is used to obtain near-optimal schedules of a batch process. [ABSTRACT FROM AUTHOR]

In this study, a deep learning-based workflow designed for the segmentation and 3D modeling of bones in cone beam computed tomography (CBCT) orthopedic imaging is presented. This workflow uses a convolutional neural network (CNN), specifically a U-Net architecture, to perform precise bone segmentation even in challenging anatomical regions such as limbs, joints, and extremities, where bone boundaries are less distinct and densities are highly variable. The effectiveness of the proposed workflow was evaluated by comparing the generated 3D models against those obtained through other segmentation methods, including SegNet, binary thresholding, and graph cut algorithms. The accuracy of these models was quantitatively assessed using the Jaccard index, the Dice coefficient, and the Hausdorff distance metrics. The results indicate that the U-Net-based segmentation consistently outperforms other techniques, producing more accurate and reliable 3D bone models. The user interface developed for this workflow facilitates intuitive visualization and manipulation of the 3D models, enhancing the usability and effectiveness of the segmentation process in both clinical and research settings. The findings suggest that the proposed deep learning-based workflow holds significant potential for improving the accuracy of bone segmentation and the quality of 3D models derived from CBCT scans, contributing to better diagnostic and pre-surgical planning outcomes in orthopedic practice. [ABSTRACT FROM AUTHOR]