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]

To address the challenge of performance portability and facilitate the implementation of electronic structure solvers, we developed the basic matrix library (BML) and Parallel, Rapid O(N), and Graph-based Recursive Electronic Structure Solver (PROGRESS) library. The BML implements linear algebra operations necessary for electronic structure kernels using a unified user interface for various matrix formats (dense and sparse) and architectures (CPUs and GPUs). Focusing on density functional theory and tight-binding models, PROGRESS implements several solvers for computing the single-particle density matrix and relies on BML. In this paper, we describe the general strategies used for these implementations on various computer architectures, using OpenMP target functionalities on GPUs, in conjunction with third-party libraries to handle performance critical numerical kernels. We demonstrate the portability of this approach and its performance in benchmark problems. [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]

Consider a graph G = (V , E) and a function f : V → { 0 , 1 , 2 }. A vertex u with f (u) = 0 is defined as undefended by f if it lacks adjacency to any vertex with a positive f -value. The function f is said to be a weak Roman dominating function (WRD function) if, for every vertex u with f (u) = 0 , there exists a neighbor v of u with f (v) > 0 and a new function f ′ : V → { 0 , 1 , 2 } defined in the following way: f ′ (u) = 1 , f ′ (v) = f (v) − 1 , and f ′ (w) = f (w) , for all vertices w in V ∖ { u , v } ; so that no vertices are undefended by f ′. The total weight of f is equal to ∑ v ∈ V f (v) , and is denoted as w (f). The Weak Roman domination number denoted by γ r (G) , represents m i n { w (f) | f is a WRD function of G }. For a given graph G , the problem of finding a WRD function of weight γ r (G) is defined as the Minimum Weak Roman domination problem. The problem is already known to be NP-hard for bipartite and chordal graphs. In this paper, we further study the algorithmic complexity of the problem. We prove the NP-hardness of the problem for star convex bipartite graphs and comb convex bipartite graphs, which are subclasses of bipartite graphs. In addition, we show that for the bounded degree star convex bipartite graphs, the problem is efficiently solvable. We also prove the NP-hardness of the problem for split graphs, a subclass of chordal graphs. On the positive side, we present a polynomial-time algorithm to solve the problem for P 4 -sparse graphs. Further, we have presented some approximation results. [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]

Multi-view clustering considers the diversity of different views and fuses these views to produce a more accurate and robust partition than single-view clustering. It is a key problem of multi-view clustering research to allocate each view reasonably based on its contribution value. In this paper, we propose a weighted multi-view clustering model via sparse graph learning to cope with allocation of different views. The proposed idea is to assign different view weights instead of equal view weights to learn a high-quality shared similarity matrix for multi-view clustering. In our new proposed method, it can consider the clustering capacity heterogeneity of different views in fusion by assigning a weight for each view so that each view special feature are fully excavated, and improve the performance of multi-view clustering. Moreover, our proposed method can directly obtained cluster indicators by imposing low rank constraints without any post-processing operations. In addition, our model is proposed based on sparse graph, so that the outliers and noise in each view data are well handled and the robustness of the algorithm is effectively guaranteed. Finally, numerous experimental results are conducted on different sizes benchmark datasets, and show that the performance of our algorithm is quite satisfactory. The code of our proposed method is publicly available at https://github.com/zhoujie05/A-weighted-multi-view-clustering-via-sparse-graph-learning. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a graph where V and E are the vertex and edge sets, respectively. For two disjoint subsets A and B of V , we say A dominates B if every vertex of B is adjacent to at least one vertex of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a transitive partition of size k if V i dominates V j for all 1 ≤ i < j ≤ k. In this article, we study a variation of transitive partition, namely 2- transitive partition. For two disjoint subsets A and B of V , we say A 2- dominates B if every vertex of B is adjacent to at least two vertices of A. A vertex partition π = { V 1 , V 2 , ... , V k } of G is called a 2- transitive partition of size k if V i 2 -dominates V j for all 1 ≤ i < j ≤ k. The Maximum 2- Transitivity Problem is to find a 2 -transitive partition of a given graph with the maximum number of parts. We show that the decision version of this problem is NP-complete for chordal and bipartite graphs. On the positive side, we design three linear-time algorithms for solving Maximum 2- Transitivity Problem in trees, split, and bipartite chain graphs. [ABSTRACT FROM AUTHOR]

Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such a route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer B (e.g. due to limited energy resources of the searcher). The objective is to cover all the edges of a tree T using the minimum number of routes, each starting and ending at the root and each being of length at most B. To this end, we analyze the following natural greedy tree traversal process that is based on decomposing a depth first search traversal into a sequence of limited length routes. Given any arbitrary depth first search traversal R of the tree T, we cover R with routes R 1 , ... , R l , each of length at most B such that: R i starts at the root, reaches directly the farthest point of R visited by R i - 1 , then R i continues along the path R as far as possible, and finally R i returns to the root. We call the above algorithm piecemeal-DFS and we prove that it achieves the asymptotically minimal number of routes l, regardless of the choice of R. Our analysis also shows that the total length of the traversal (and thus the traversal time) of piecemeal-DFS is asymptotically minimum over all energy-constrained exploration strategies. The fact that R can be chosen arbitrarily means that the exploration strategy can be constructed in an online fashion when the input tree T is not known in advance. Each route R i can be constructed without any knowledge of the yet unvisited part of T. Surprisingly, our results show that depth first search is efficient for energy constrained exploration of trees, even though it is known that the same does not hold for energy constrained exploration of arbitrary graphs. [ABSTRACT FROM AUTHOR]

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a ▵ -free planar graph G, there exists an independent set A L such that G [ V G \ A L ] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the N P -completeness of the decision problem of determining an independent set A such that G [ V G \ A ] is 2-choosable for ▵ -free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G, such that the induced subgraph G [ V G \ A ] is 2-choosable. We establish that this problem is N P -hard to approximate within a factor of | V G | 1 - ϵ for any ϵ > 0 , for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F ⊆ E G of minimum cardinality such that the spanning subgraph G [ E G \ F ] is 2-choosable. We prove that this problem can be approximated within a factor of O (log | V G |) . [ABSTRACT FROM AUTHOR]

In the current era of mobile edge networks, a significant challenge lies in overcoming the limitations posed by limited edge storage and computational resources. To address these issues, accurate network traffic prediction has emerged as a promising solution. However, due to the intricate spatial and temporal dependencies inherent in mobile edge network traffic, the prediction task remains highly challenging. Recent spatio-temporal neural network algorithms based on graph convolution have shown promising results, but they often rely on pre-defined graph structures or learned parameters. This approach neglects the dynamic nature of short-term relationships, leading to limitations in prediction accuracy. To address these limitations, we introduce Ada-ASTGCN, an innovative attention-based adaptive spatio-temporal graph convolutional network. Ada-ASTGCN dynamically derives an optimal graph structure, considering both the long-term stability and short-term bursty evolution. This allows for more precise spatio-temporal network traffic prediction. In addition, we employ an alternative training approach during optimization, replacing the traditional end-to-end training method. This alternative training approach better guides the learning direction of the model, leading to improved prediction performance. To validate the effectiveness of Ada-ASTGCN, we conducted extensive traffic prediction experiments on real-world datasets. The results demonstrate the superior performance of Ada-ASTGCN compared to existing methods, highlighting its ability to accurately predict network traffic in mobile edge networks. [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]

Given a graph G with vertex set V and edge set E , a vertex set D is a dominating set (DS) of G , if every vertex v ∈ V is either in D or adjacent to a vertex in D. If D is a DS of G and for every vertex v ∈ V ∖ D there exists a vertex u ∈ D adjacent to v such that (D ∖ { u }) ∪ { v } is also a DS of G , then D is a secure dominating set (SDS). The minimum secure dominating set problem (MinSDS) is to find an SDS of G with the minimum cardinality. In this paper, we design PTASs for MinSDS on planar graphs and growth-bounded graphs, that is, the computed solutions approximate the optimal value within factor (1 + ɛ) for any constant ɛ ∈ (0 , 1). [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]

ABSTRACT This paper presents a High Gain Metasurface (HGM) antenna design optimized for IoT applications. The antenna operates at a 5.8 GHz frequency and utilizes a quarter‐wavelength unit cell structure. The design employs a Graph Sample and Aggregate‐Attention Network (GSAAN) to enhance the transmission characteristics of the metasurface. To optimize the performance of GSAAN, the Giza Pyramids Construction Algorithm (GPCN) is applied to adjust the weight parameters, leading to significant improvements in radiation efficiency, bandwidth, gain, directivity, and return loss. The proposed HGM antenna is simulated in MATLAB 2023b, where it demonstrates substantial performance gains over existing methods. Specifically, the proposed design achieves 28.34% higher gain compared to the MSA‐RHCOA method, 24.47% improvement over HGM‐AD‐MATCS, 26.34% better gain than BR‐HGA‐PGM, and a 32.12% gain increase relative to MSA‐Hyb‐ADSA‐HMSOA. These enhancements make the proposed antenna design a competitive solution for high‐gain applications in wireless communication, satellite communication, and radar systems. The integration of GSAAN with GPCN optimization in the HGM antenna design enables the creation of highly directive radiation patterns, making it well‐suited for IoT applications that require high performance and reliability. The results of this study demonstrate the effectiveness of the proposed approach in achieving superior antenna performance, positioning it as a strong alternative to existing metasurface antenna designs. [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]

Large-scale graph layout remains a prominent focus in graph visualization research. While the stress model excels in representing global structure, its speed lags behind the spring-electric model, and its local structure quality is suboptimal. This paper proposed a graph layout algorithm, aimed at enhancing the efficiency of layout while preserving global structure and improving local quality. The model first utilized graph compression based on neighbor structure to generate a hierarchical graph structure, and then used the node optimal placement algorithm to initialize the node coordinates. Next, it improved the local quality of layout using a SGD layout algorithm based on positive and negative samples, and further enhanced the layout speed through multi-level algorithm. Finally, comparative experiments with existing layout models on 30 datasets of different scales demonstrate the effectiveness of the proposed model in terms of efficiency, layout quality and visualization. [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]

For a simple, undirected graph G (V , E) without isolated vertices, a function h : V → { ϕ , { 1 } , { 2 } , { 1 , 2 } } which satisfies the following two conditions is called a total 2-rainbow dominating function (T2RDF) of G. (i) For all u ∈ V , if h (u) = ϕ then ∪ v ∈ N (u) h (v) = { 1 , 2 } and (ii) Every u ∈ V with h (u) ≠ ϕ is adjacent to a vertex v with h (v) ≠ ϕ. The weight of a T2RDF h of G is the value h (V) = ∑ u ∈ V | h (u) |. The total 2-rainbow domination number is the minimum weight of a T2RDF on G and is denoted by γ t r 2 (G). The minimum total 2-rainbow domination problem (MT2RDP) is to find a T2RDF of minimum weight in the input graph. In this article, we show that the problem of deciding if G has a T2RDF of weight at most l for star convex bipartite graphs, comb convex bipartite graphs, split graphs and planar graphs is NP-complete. On the positive side, we show that MT2RDP is linear time solvable for threshold graphs, chain graphs and bounded tree-width graphs. On the approximation point of view, we show that MT2RDP cannot be approximated within (1 −) ln | V | for any > 0 unless P=NP and also propose 2 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for it. Further, we show that MT2RDP is APX-complete for graphs with maximum degree 4. Next, it is shown that domination problem and the total 2-rainbow domination problems are not equivalent in computational complexity aspects. Finally, an integer linear programming formulation for MT2RDP is presented. [ABSTRACT FROM AUTHOR]

Tensegrity structures, characterized by enhanced stiffness, slender struts, and superior buckling resistance, have found wide-ranging applications in fields such as engineering, architecture, art, biology, and robotics, attracting extensive attention from researchers. The form-finding process, a critical step in the design of tensegrity structures, aims to discover the self-equilibrated configuration that satisfies specific design requirements. Traditional form-finding methods based on force density often require repeated steps of eigenvalue decomposition and singular value decomposition, making the process complex. In contrast, this paper introduces a new intelligent form-finding algorithm that uses the force density method and combines the Coati optimization algorithm with Graph Neural Networks. This algorithm avoids the complex steps of eigenvalue and singular value decomposition and integrates the physical knowledge of the structure, making the form-finding process faster and more accurate. In this algorithm, various force densities are initially randomized and input into a trained Graph Neural Networks to predict a fitness function's value. Through optimizing the constrained fitness function, the algorithm determines the appropriate structural force density and coordinates, thereby completing the form-finding process of the structure. The paper presents seven typical tensegrity structure examples and compares various form-finding methods. The results of numerical examples show that the method proposed in this paper can find solutions that align with the super-stable line more quickly and accurately, demonstrating its potential value in practical applications. [ABSTRACT FROM AUTHOR]

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization problems. It is known for its inherent hardness of approximation. We focus on the well known minimum-degree greedy algorithm for this problem. This algorithm iteratively chooses a minimum degree vertex in the graph, adds it to the solution and removes its neighbors, until the remaining graph is empty. The approximation ratios of this algorithm have been widely studied, where it is augmented with an advice that tells the greedy algorithm which minimum degree vertex to choose if it is not unique. Our main contribution is a new mathematical theory for the design of such greedy algorithms for MIS with efficiently computable advice and for the analysis of their approximation ratios. Using this theory we obtain the ultimate approximation ratio of 5/4 for greedy algorithms on graphs with maximum degree 3, which completely solves an open problem from the paper by Halldórsson and Yoshihara (in: Staples, Eades, Katoh, Moffat (eds) Algorithms and computations—ISAAC '95, in 2026 LNCS, Springer, Berlin, Heidelberg, 1995). Our algorithm is the fastest currently known algorithm for MIS with this approximation ratio on such graphs. We also obtain a simple and short proof of the (Δ + 2) / 3 -approximation ratio of any greedy algorithms on graphs with maximum degree Δ , the result proved previously by Halldórsson and Radhakrishnan (Nord J Comput 1:475–492, 1994). We almost match this ratio by showing a lower bound of (Δ + 1) / 3 on the ratio of a greedy algorithm that can use an advice. We apply our new algorithm to the minimum vertex cover problem on graphs with maximum degree 3 to obtain a substantially faster 6/5-approximation algorithm than the one currently known. We complement our algorithmic, upper bound results with lower bound results, which show that the problem of designing good advice for greedy algorithms for MIS is computationally hard and even hard to approximate on various classes of graphs. These results significantly improve on the previously known hardness results. Moreover, these results suggest that obtaining the upper bound results on the design and analysis of the greedy advice is non-trivial. [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]

In light of the recent pandemic and the shortage of vaccinations during their roll-out, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses also proved to be highly uncertain, with manufacturers not being able to deliver the promised amount of vaccines on time. In this paper, we study the robust version of this problem and its generalization to matchings on arbitrary graphs. By exploring the problem, we show that it is weakly NP-hard for a constant number of scenarios and strongly NP-hard else. Further, we propose a pseudo-polynomial algorithm for the weakly NP-hard subproblem with a constant number of scenarios and time between both doses. Finally, we perform computational experiments to better understand the behavior of the problem. [ABSTRACT FROM AUTHOR]

Cancer-associated adipocytes (CAAs) have emerged as pivotal players in various cancers, particularly in such as breast cancer, significantly influencing their progression and therapy resistance. Understanding the adipocytes/cancer cells crosstalk is crucial for effective treatment strategies. Raman spectroscopy, a label-free optical technique, offers potential for characterizing biological samples by providing chemical-specific information. In this study, we used Raman spectroscopy and Trajectory Inference methods, specifically the Partition-based graph abstraction algorithm, to investigate the interactions between 3T3-L1 differentiated adipocytes and MDA-MB-231 breast cancer cells in a 2D co-culture model. We demonstrate the existence of subpopulations of adipocytes and the molecular changes associated with CAAs phenotype. This work contributes to understanding the role of CAAs in breast cancer progression and may guide the development of targeted therapies disrupting this interaction. [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]

The intelligent design of complex transportation nodes is an important way to improve urban transportation efficiency and safety. However, currently, there are still problems with low data acquisition and processing accuracy and high-technology application costs in complex transportation nodes. Therefore, the research attempts to achieve the intelligent design of complex traffic node organizations based on digital analogue-driven and integrated building information models and optimization graph convolution algorithms. It aims to achieve real-time monitoring and analysis of traffic information to improve the overall performance of the transportation system. These experiments confirmed that the studied BIM could achieve full lifecycle management of urban interchanges, and could achieve strain analysis and trend prediction based on time series. When the organizational members were 122, the information channels for smart stations based on research technology were 241, which improved information efficiency by more than 90%. When the sensor node was 48, the predicted values of the research model based on the optimization graph convolution algorithm were consistent with the actual values, with a prediction accuracy of 95%. Therefore, the technology studied in this study can provide reliable solutions for the design of complex traffic nodes and support traffic management decisions. [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 fuzzy concept lattice is one of the effective tools for data mining, and granular reduction is one of its significant research contents. However, little research has been done on granular reduction at different granularities in formal fuzzy contexts (FFCs). Furthermore, the complexity of the composition of the fuzzy concept lattice limits the interest in its research. Therefore, how to simplify the concept lattice structure and how to construct granular reduction methods with granularity have become urgent issues that need to be investigated. To this end, firstly, the concept of an object granule with granularity is defined. Secondly, two reduction algorithms, one based on Boolean reasoning and the other on a graph-theoretic heuristic, are formulated while keeping the structure of this object granule unchanged. Further, to simplify the structure of the fuzzy concept lattice, a partial order relation with parameters is proposed. Finally, the feasibility and effectiveness of our proposed reduction approaches are verified by data experiments. [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]

Given a graph G = (V , E) , the problem of Graph Burning is to find a sequence of nodes from V , called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a 3 -approximation algorithm for general graphs and a 2 -approximation algorithm for trees. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose (1) A 2. 7 5 -approximation algorithm for a cactus graph (undirected), (2) A 3 -approximation algorithm for multi-rooted directed trees (polytree) and (3) A 1. 9 0 5 -approximation algorithm for the single-rooted directed tree (arborescence). We implement all three approximation algorithms, and the results are shown for randomly generated cactus graphs, multi-rooted directed trees and single-rooted directed trees. [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]

The Jacobian-free Newton-Krylov (JFNK) method is a widely used and flexible numerical method for solving the neutronic/thermal-hydraulic coupling system. The main property of JFNK is that the Jacobian-vector product is evaluated approximately by finite difference, avoiding the forming and storage of Jacobian explicitly. However, the lack of an efficient preconditioner is a major bottleneck for the JFNK method, leading to poor convergence. The finite difference Jacobian-based Newton-Krylov (DJNK) method is another advanced numerical method, in which the Jacobian matrix is formed and stored explicitly. The DJNK method can provide a better preconditioner for Krylov iteration than JFNK. However, how to compute the Jacobian matrix efficiently and automatically is a key issue for the DJNK method. By fully utilizing the sparsity of the Jacobian matrix and graph coloring algorithm, the Jacobian can be computed efficiently. Unfortunately, when there are dense rows/blocks, a huge computational burden will emerge due to the lack of sparsity, resulting in the extremely poor efficiency of Jacobian computation. In this work, a Jacobian-split Newton-Krylov (JSNK) method is proposed to resolve the dense row/block problem by combining the advantages of JFNK and DJNK. The main feature of the JSNK method is to split the Jacobian matrix into sparse and dense parts. The sparse part of the Jacobian matrix is explicitly constructed using the graph coloring algorithm while for the dense part, the Jacobian-vector product is approximated by finite difference. The computational complexity of the JSNK method is analyzed and compared to the JFNK method and the DJNK method from theoretical and experimental aspects and under different meshes. A simplified two-dimensional (2-D) high-temperature gas-cooled reactor (HTR) model and a simplified 2-D pressurized water reactor model are utilized to demonstrate the superiority of the JSNK method. The numerical results show that the JSNK method successfully resolved the dense rows/blocks. More importantly, its efficiency significantly outperforms the JFNK method and the DJNK method. [ABSTRACT FROM AUTHOR]

A minimal separator of a graph G is a set S⊆V(G) such that there exist vertices a,b∈V(G)⧹S with the property that S separates a from b in G, but no proper subset of S does. For an integer k≥0, we say that a minimal separator is k‐simplicial if it can be covered by k cliques and denote by Gk the class of all graphs in which each minimal separator is k‐simplicial. We show that for each k≥0, the class Gk is closed under induced minors, and we use this to show that the Maximum Weight Stable Set problem can be solved in polynomial time for Gk. We also give a complete list of minimal forbidden induced minors for G2. Next, we show that, for k≥1, every nonnull graph in Gk has a k‐simplicial vertex, that is, a vertex whose neighborhood is a union of k cliques; we deduce that the Maximum Weight Clique problem can be solved in polynomial time for graphs in G2. Further, we show that, for k≥3, it is NP‐hard to recognize graphs in Gk; the time complexity of recognizing graphs in G2 is unknown. We also show that the Maximum Clique problem is NP‐hard for graphs in G3. Finally, we prove a decomposition theorem for diamond‐free graphs in G2 (where the diamond is the graph obtained from K4 by deleting one edge), and we use this theorem to obtain polynomial‐time algorithms for the Vertex Coloring and recognition problems for diamond‐free graphs in G2, and improved running times for the Maximum Weight Clique and Maximum Weight Stable Set problems for this class of graphs. [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]

[Objective] Recently, underground space disasters have occurred with increasing frequency, highlighting the urgent need for a comprehensive, multidimensional support system for emergency communication. A key task in emergency communication for underground spaces is the rapid reorganization of communication networks to relay disaster information in real time. Unmanned aerial vehicles(UAVs), with their flexible deployment, unmanned operation, and all-terrain mobility, can play a vital role in emergency rescue efforts. In the event of disasters such as fires, collapses, or floods, UAVs can quickly access affected areas and establish stable ad-hoc networks using their onboard communication devices. UAVs can promptly transmit the collected disaster information back to the rescue center, thereby enhancing the efficiency of rescue operations. However, while extensive research has been conducted on UAV applications in low-altitude areas, further development is necessary for their use in underground spaces. Particularly, there is a lack of research on experimental platforms that integrate scientific research and teaching. This gap has resulted in a disconnect between the educational content and real-world scenarios. Therefore, establishing a scenario-based teaching and practice platform for emergency communication networks in underground spaces is essential. By enhancing practical teaching content, we can effectively guide students in learning modern emergency communication network technologies, ensuring a strong connection between theoretical instruction and real-world applications. [Methods] In this paper, we employ hypergraph theory to abstract the rapidly changing network topology into a dynamically evolving hypergraph, modeling the evolution of interference relations through the insertion and deletion of superedges. Specifically, we reformulate the dynamic channel selection problem in UAV communication networks as a hypergraph coloring problem. To adapt to the dynamic network topology, we leverage reinforcement learning theory to enhance the traditional hypergraph coloring algorithm and develop a dynamic hypergraph coloring algorithm. Additionally, when the topology of the UAV communication network changes, the traditional greedy algorithm requires recalculation at each time slot, whereas the Q-learning algorithm can quickly converge based on prior learning. Building on this discussion, we propose a dynamic channel selection algorithm based on the Q-learning framework, which can adjust the learning rate parameters according to the rate of topological changes. [Results] To validate the effectiveness of our proposed algorithm, we conduct extensive simulation experiments to observe how the proportion of link conflicts in the network changes with varying algorithm iterations and UAV flight speeds. Additionally, we analyze the changes in average throughput across different network sizes, comparing the Q-learning algorithm to the greedy algorithm. The simulation results demonstrate that our algorithm can dynamically adjust the learning rate parameters based on the topological change rate of the UAV communication networks, achieving an optimal trade-off between algorithm performance and convergence speed. And the network performance of this algorithm is better than that of the greedy algorithm. [Conclusions] In conclusion, we utilize hypergraph theory to design an adaptive channel selection algorithm based on the Q-learning framework and establish a simulation experiment platform using ns-3 simulation software. Specifically, we employ the ns-3 platform to create a network simulation experiment for an underground space emergency scenario, helping students apply their theoretical knowledge of communication networks to practical engineering contexts. This work lays a solid foundation for developing a simulation teaching platform for UAV emergency communication networks within the interdisciplinary integration of electronic information science and emergency management. [ABSTRACT FROM AUTHOR]

Shared autonomous electric vehicles (SAEVs) have recently attracted significant public interest. The dynamic ride-sharing using SAEVs appears to have the advantages of reducing travel costs and relieving urban traffic congestion. It is meant to improve the practical application value of the dynamic ride-sharing mode of SAEVs. In this paper, to reduce the solution time complexity, a pre-matching algorithm considering the driverless and charging characteristics of SAEVs is developed, and then a two-stage, graph-based many-to-one ride-matching (GMOM) algorithm is proposed for the dynamic ride-sharing problem in the Autonomous Mobility-on-Demand system (AMOD). The dataset from DiDi during the peak travel time and the real-time traffic flow from the AutoNavi map were used to verify the effects of the method. The results demonstrate that the GMOM approach can effectively reduce computational complexity and improve user satisfaction. The dynamic ride-sharing mode based on the GMOM algorithm has a 5.67% higher service rate and 45.56% more vehicle calls than the non-ride-sharing mode under the same conditions. It is found that the cost-effectiveness of using ride-sharing services is relatively high for 10–20 km trips during peak travel time and the dynamic ride-sharing may extend total travel time but will reduce passengers' waiting time. [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]

Graph coloring is an NP-hard combinatorial optimization problem with significant implications in both theoretical and practical contexts due to its complexity and extensive applicability. In this work, a novel approach is proposed to address the graph coloring problem through a parallel discrete Harmony Search algorithm, termed PDHSCol. By harnessing the robustness of the Harmony Search algorithm and integrating parallel processing, our algorithm enhances performance by concurrently generating and evaluating multiple solutions. Implemented in MATLAB, PDHSCol was evaluated using a variety of DIMACS benchmark instances. The experimental results demonstrate that the algorithm performs effectively and yields promising improvements over various other methods, highlighting its potential to deliver high-quality solutions. [ABSTRACT FROM AUTHOR]

In this article, we provide a unified and simplified approach to derandomize central results in the area of fault-tolerant graph algorithms. Given a graph \(G\) , a vertex pair \((s,t)\in V(G)\times V(G)\) , and a set of edge faults \(F\subseteq E(G)\) , a replacement path \(P(s,t,F)\) is an \(s\) - \(t\) shortest path in \(G\setminus F\). For integer parameters \(L,f\) , a replacement path covering (\(\mathsf{RPC}\)) is a collection of subgraphs of \(G\) , denoted by \(\mathcal{G}_{L,f}=\{G_{1},\ldots,G_{r}\}\) , such that for every set \(F\) of at most \(f\) faults (i.e., \(|F|\leq f\)) and every replacement path \(P(s,t,F)\) of at most \(L\) edges, there exists a subgraph \(G_{i}\in\mathcal{G}_{L,f}\) that contains all the edges of \(P\) and does not contain any of the edges of \(F\). The covering value of the \(\mathsf{RPC}\) \(\mathcal{G}_{L,f}\) is then defined to be the number of subgraphs in \(\mathcal{G}_{L,f}\). In the randomized setting, it is easy to build an \((L,f)\) - \(\mathsf{RPC}\) with covering value of \(O(\max\{L,f\}^{\min\{L,f\}}\cdot\min\{L,f\}\cdot \log n)\) , but to this date, there is no efficient deterministic algorithm with matching bounds. As noted recently by Alon et al. (ICALP 2019), this poses the key barrier for derandomizing known constructions of distance sensitivity oracles and fault-tolerant spanners. We show the following: — There exist efficient deterministic constructions of \((L,f)\) - \(\mathsf{RPC}\) s whose covering values almost match the randomized ones, for a wide range of parameters. Our time and value bounds improve considerably over the previous construction of Parter (DISC 2019). Our algorithms are based on the introduction of a novel notion of hash families that we call HM hash families. We then show how to construct these hash families from (algebraic) error correcting codes such as Reed–Solomon codes and Algebraic-Geometric codes. — For every \(L,f\) , and \(n\) , there exists an \(n\) -vertex graph \(G\) whose \((L,f)\) - \(\mathsf{RPC}\) covering value is \(\Omega(L^{f})\). This lower bound is obtained by exploiting connections to the problem of designing sparse fault-tolerant breadth first search (BFS) structures. An application of our above deterministic constructions is the derandomization of the algebraic construction of the distance sensitivity oracle by Weimann and Yuster (FOCS 2010). The preprocessing and query time of our deterministic algorithm nearly match the randomized bounds. This resolves the open problem of Alon et al. (ICALP 2019). Additionally, we show a derandomization of the randomized construction of vertex fault-tolerant spanners by Dinitz and Krauthgamer (PODC 2011) and Braunschvig et al. (Theor. Comput. Sci., 2015). The time complexity and the size bounds of the output spanners nearly match the randomized counterparts. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Beijing University of Technology is the property of Journal of Beijing University of Technology, Editorial Department and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Contemporary graph learning algorithms are not well-suited for large molecules since they do not consider the hierarchical interactions among the atoms, which are essential to determining the molecular properties of macromolecules. In this work, we propose Multiresolution Graph Transformers (MGT), the first graph transformer architecture that can learn to represent large molecules at multiple scales. MGT can learn to produce representations for the atoms and group them into meaningful functional groups or repeating units. We also introduce Wavelet Positional Encoding (WavePE), a new positional encoding method that can guarantee localization in both spectral and spatial domains. Our proposed model achieves competitive results on three macromolecule datasets consisting of polymers, peptides, and protein-ligand complexes, along with one drug-like molecule dataset. Significantly, our model outperforms other state-of-the-art methods and achieves chemical accuracy in estimating molecular properties (e.g., highest occupied molecular orbital, lowest unoccupied molecular orbital, and their gap) calculated by Density Functional Theory in the polymers dataset. Furthermore, the visualizations, including clustering results on macromolecules and low-dimensional spaces of their representations, demonstrate the capability of our methodology in learning to represent long-range and hierarchical structures. Our PyTorch implementation is publicly available at https://github.com/HySonLab/Multires-Graph-Transformer. [ABSTRACT FROM AUTHOR]