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]

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]

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.)

Given a graph G = (V , E) with n = | V | vertices, the graph coloring problem is defined as Find a color vector C = (c (v)) , where c (v) ∈ { 1 , 2 , ... , n } denotes the color of vertex v ∈ V , such that no monochromatic edge exists in G and the span , the total number of distinct colors in C , is minimized. Since the problem is NP-complete, a greedy coloring is commonly used for solving it. Greedy coloring visits the vertices of G following an order S , and while visiting a vertex v , it puts the minimum color absent in all neighbors of v. We show that the orders producing span ≤ k , where k ≤ n is a positive integer, can be partitioned into disjoint subsets of equivalent orders. Next, we propose a selective search (SS) algorithm, which takes ρ as an input parameter, selects ≥ ρ orders each from a different set of equivalent orders with high probability, applies greedy coloring on them, and returns the color vector with minimum span. We analytically show that SS performs better than greedy coloring with high probability by evaluating the same number of orders. We propose an incremental search heuristic (ISH), which ρ 1 times execute SS with parameter ρ 2 and returns the color vector with minimum span. A parallel version of ISH called PISH is also proposed, executing ρ 1 SS calls in parallel. We show that ISH hits an optimum coloring for a graph G = (V , E) with χ (G) (Δ (G) + 1) ≤ n e in expected O (| V | + | E |) time and space complexities. We have evaluated ISH and PISH on 136 challenging benchmarks and shown that they significantly outperform 10 existing state-of-the-art algorithms. Finally, we validated our theoretical findings by evaluating ISH and greedy coloring on random graphs. [ABSTRACT FROM AUTHOR]

A Roman { 3 } -dominating function on a graph G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that for any vertex u ∈ V (G) , if f (u) = 0 , then ∑ v ∈ N G (u) f (v) ≥ 3 , and if f (u) = 1 , then ∑ v ∈ N G (u) f (v) ≥ 2. The weight of a Roman { 3 } -dominating function f is the sum f (V (G)) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is called the Roman { 3 } -domination number of G and is denoted by γ { R 3 } (G). Given a graph G , Roman { 3 } - domination asks to find the minimum weight of a Roman { 3 } -dominating function on G. In this paper, we study the algorithmic aspects of Roman { 3 } - domination on various graph classes. We show that the decision version of Roman { 3 } - domination remains NP -complete for chordal bipartite graphs, planar graphs, star-convex bipartite graphs, and chordal graphs. We show that Roman { 3 } - domination cannot be approximated within a ratio of (1 3 − ɛ) ln | V (G) | for any ɛ > 0 unless P = NP for bipartite graphs as well as chordal graphs, whereas Roman { 3 } - domination can be approximated within a factor of O (ln Δ) for graphs having maximum degree Δ. We also show that Roman { 3 } - domination is APX -complete for graphs with maximum degree 4. On the positive side, we show that Roman { 3 } - domination can be solved in linear time for chain graphs and cographs. [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]

This article presents a matching algorithm for bipartite graphs containing repetitive structures and represented by intension as Set-Based Graphs. Under certain conditions on the structure of the graphs, the computational cost of this novel algorithm is not affected by the cardinality of the sets of vertices and edges. The main application of the algorithm is that of matching large Equation-Based Models where provided that most equations are defined using for loop statements that iterate over vectors of unknown variables, the computational cost becomes independent of the growth of the vectors involved. Besides introducing the algorithm, the article describes its implementation in a Modelica compiler and studies its performance over different test models. [ABSTRACT FROM AUTHOR]

A Grundy n-coloring of a graph G is a proper vertex coloring in which every vertex in V (G) colored with Cn is adjacent with all Cn-1 colors. The Grundy cloring or Grundy number Γ(G) is the maximum number which can also be predicted by greedy coloring strategy by choosing some vertex order to obtain maximum colors. In this paper, we provide some exact values for Grundy coloring of degree splitting graph of wheel graph, helm graph, sunlet graph, crown graph and Friendship graph which are denoted by [DS(Wn)], [DS(Hn)], [DS(Sn)], [DS(Hn,n)] and Γ[DS(Fn)] respectively. [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]

Modifying network results is the most intuitive way to inject domain knowledge into network detection algorithms to improve their performance. While advances in computation scalability have made detecting large‐scale networks possible, the human ability to modify such networks has not scaled accordingly, resulting in a huge 'interaction gap'. Most existing works only support navigating and modifying edges one by one in a graph visualization, which causes a significant interaction burden when faced with large‐scale networks. In this work, we propose a novel graph pattern mining algorithm based on the minimum description length (MDL) principle to partition and summarize multi‐feature and isomorphic sub‐graph matches. The mined sub‐graph patterns can be utilized as mediums for modifying large‐scale networks. Combining two traditional approaches, we introduce a new coarse‐middle‐fine graph modification paradigm (i.e. query graph‐based modification →$\rightarrow$ sub‐graph pattern‐based modification →$\rightarrow$ raw edge‐based modification). We further present a graph modification system that supports the graph modification paradigm for improving the scalability of modifying detected large‐scale networks. We evaluate the performance of our graph pattern mining algorithm through an experimental study, demonstrate the usefulness of our system through a case study, and illustrate the efficiency of our graph modification paradigm through a user study. [ABSTRACT FROM AUTHOR]

We introduce time‐varying extremum graph (tveg), a topological structure to support visualization and analysis of a time‐varying scalar field. The extremum graph is a sub‐structure of the Morse–Smale complex. It captures the adjacency relationship between cells in the Morse decomposition of a scalar field. We define the tveg as a time‐varying extension of the extremum graph and demonstrate how it captures salient feature tracks within a dynamic scalar field. We formulate the construction of the tveg as an optimization problem and describe an algorithm for computing the graph. We also demonstrate the capabilities of tveg towards identification and exploration of topological events such as deletion, generation, split and merge within a dynamic scalar field via comprehensive case studies including a viscous fingers and a 3D von Kármán vortex street dataset. [ABSTRACT FROM AUTHOR]

A set D ⊆ V of a graph G = (V , E) is called a connected power dominating set of G if G [ D ] , the subgraph induced by D , is connected and every vertex in the graph can be observed from D , following the two observation rules for power system monitoring: Rule 1 : if v ∈ D , then v can observe itself and all its neighbors, and Rule 2 : for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Given a graph G , Minimum Connected Power Domination is to find a connected power dominating set of minimum cardinality of G and Decide Connected Power Domination is the decision version of Minimum Connected Power Domination. Decide Connected Power Domination is known to be N P -complete for general graphs. In this paper, we prove that Decide Connected Power Domination remains N P -complete for star-convex bipartite graphs, perfect elimination bipartite graphs and split graphs. This answers some open problems posed in [B. Brimkov, D. Mikesell and L. Smith, Connected power domination in graphs, J. Comb. Optim. 38(1) (2019) 292–315]. On the positive side, we show that Minimum Connected Power Domination is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination cannot be approximated within (1 −) ln | V | for any > 0 unless P = N P , for bipartite graphs as well as for chordal graphs. Finally, we show that Minimum Connected Power Domination is APX -hard for bounded degree graphs. [ABSTRACT FROM AUTHOR]

The Linear Layout of Graphs problem asks, given a graph G and a positive integer k , whether G admits a layout consisting of a linear ordering of its vertices and a partition of its edges into k sets such that the edges in each set meet some special requirements. Specific linear layouts include k -Stack Layout, k -Queue Layout, k -Arch Layout, Mixed s -Stack q -Queue Layout and others. In this paper, we present a unified approach for kernelization of these linear layout problems parameterized by the vertex cover number τ of the input graph. The key point underlying our approach is to partition each set of related vertices into two distinct subsets with respect to the specific layouts, which immediately leads to some efficient reduction rules. We first apply this approach to the Mixed s -Stack q -Queue Layout problem and show that it admits a kernel of size 2 (τ) , which results in an algorithm running in time (2 2 (τ) + τ ⋅ | V |) , where | V | denotes the size of the input graph. Our work does not only confirm the existence of a fixed-parameter tractable algorithm for this problem mentioned by Bhore et al. (J. Graph Algorithms Appl. 2022), but also derives new results for the k -Stack Layout problem and for the k -Queue Layout problem respectively. We also employ this approach to the Upward k -Stack Layout problem and obtain a new result improving that presented by Bhore et al. (GD 2021). Last but not least, we use this approach to the k -Arch Layout problem and obtain a similar result. [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]