Hejiao Huang

Structural graph queries involving connectivity constraints are fundamental primitives in modern data management and analytics. Compared with degree- and edge-based variants, connectivity-based γ-quasi-cliques (γ-CQCs) impose stronger structural constraints and fault tolerance, where robustness is measured by vertex connectivity, i.e., the minimum number of vertices whose removal disconnects the subgraph. However, processing such queries on large graphs remains computationally challenging. In this paper, we study the efficient execution of the Maximum Connectivity-based γ-Quasi-Clique (MCQC) query, which seeks the γ-CQC with the largest number of vertices. The problem is NP-hard, and the non-hereditary nature of vertex connectivity invalidates many traditional pruning techniques, posing significant challenges for exact query processing. Existing solutions rely on generic optimization formulations and exhibit poor scalability in practice. To address these challenges, we propose MCQC-TD, a specialized exact branch-and-bound framework for the MCQC query. MCQC-TD adopts a top-down search strategy and exploits a novel structural characterization of γ-CQCs to enable effective pruning and guided branching. These techniques substantially reduce the theoretical worst-case complexity compared to existing approaches. We further integrate practical query optimization techniques, including an optimized initialization strategy and a query decomposition framework, to enhance scalability on large graphs. Extensive experiments demonstrate that MCQC-TD consistently outperforms the state-of-the-art solution, achieving speedups of up to five orders of magnitude in query time.

Community search has widespread applications in areas such as advertising, friend recommendation, and protein complex identification. In this paper, we revisit the Size-bounded Community Search (SCS) problem, which aims to identify a connected subgraph containing a query vertex q and between l and h vertices, while maximizing the minimum degree of the subgraph. Existing state-of-the-art exact solutions for SCS face challenges in practical efficiency due to ineffective strategies for searching candidate solutions and suboptimal method for finding optimal solution. To address these challenges, we propose a novel branch-and-bound algorithm that efficiently locating a subset of candidate solutions with favorable structural properties, forming the basis for three progressively refined frameworks to determine the optimal solution. Furthermore, we enhance practical performance through a new heuristic, two reduction rules, and a query decomposition technique. Extensive experiments on 12 large real-world graphs demonstrate that our most efficient framework significantly outperforms state-of-the-art methods, achieving an average speedup of two orders of magnitude while consistently identifying communities with higher cohesion.

Cloud-Fog computing has emerged as an essential paradigm to support the growing demand for real-time data processing driven by the Internet of Things. By integrating the extensive computing capabilities of cloud data centres with the low-latency benefits of fog nodes, this architecture increases resource utilisation and improves quality of service. However, the dynamic and heterogeneous nature of cloud fog environments poses significant workflow scheduling challenges, especially when optimising multiple trade-offs such as latency, cost, energy consumption, and resource utilisation. This paper investigates the many-objective dynamic workflow scheduling problem under deadline constraints in container-based cloud-fog computing environments (MDWS-CoCF). Unlike existing studies that primarily focus on horizontal scaling, this work considers both vertical and horizontal scaling of containers, allowing for real-time adjustments of container configurations based on task-specific requirements. To address this complex problem, we first develop a dynamic workflow scheduling simulator that models real-world scenarios, including a variety of task categories and container scalability. Based on this simulator, we propose a Cooperative Coevolution Genetic Programming (CCGP) approach that evolves specialised heuristics for task selection, resource allocation, and container deployment to facilitate adaptive and efficient scheduling in MDWS-CoCF. Extensive simulations using real-world data traces show that the proposed CCGP approach significantly outperforms existing baseline algorithms, achieving superior performance as measured by the HyperVolume and Inverted Generational Distance metrics. The results show that the evolved heuristics are robust and effective under different dynamic scenarios, ensuring balanced optimisation of many objectives.

Discrete chaotic maps in the real number field have been widely investigated and applied to various applications. However, there has been limited focus on constructing discrete chaotic maps with complicated dynamics in the complex field. In light of this, this article proposes a 1-D complex-variable chaotic model (1-D-CCM), which can produce a multitude of 1-D complex-variable chaotic maps by combining unbounded analytic functions and locally bounded analytic functions. To illustrate the effectiveness of 1-D-CCM, we construct two 1-D complex-variable chaotic maps by combining inverse trigonometric functions and hyperbolic trigonometric functions. We provide theoretical proof of a new 1-D complex-variable chaotic map as one example to demonstrate that the generated chaotic maps satisfy the chaos definition in terms of Lyapunov exponent. Property analysis reveals distinct strange attractors and hyperchaotic behaviors for the two 1-D complex-variable chaotic maps. Performance evaluations show that the example maps of 1-D-CCM model can achieve a 0–1 test value of 1.0017, a $C_{0}$ complexity of 0.7253, a correlation dimension of 2.0242, and a sample entropy of 0.8288. Experimental results demonstrate superior performance indicators compared to other representative chaotic maps. We construct a hardware platform using a microcontroller to implement the attractors of the two new complex-variable chaotic maps. Finally, we design pseudorandom number generators to demonstrate the potential applications of the two 1-D complex-variable chaotic maps.

In this letter, we study the Multi-Size Agent Path Finding (MSAPF) problem, which is a generalization of the Multi-Agent Path Finding (MAPF) problem and has a wider range of practical applications in intelligent transportation. Compared to the well-known MAPF problem in which each agent only occupies one grid, multi-size agents in MSAPF have different sizes and may occupy multiple grids. Different sizes result in two bottlenecks in finding conflict-free paths. One is that conflicts between the shortest paths of multi-size agents are difficult to resolve, and the other is that numerous new conflicts are likely to occur when resolving one conflict. Existing MAPF algorithms are inefficient in solving MSAPF because they only consider conflicts involving a single grid or between adjacent grids, and few works focus on solving these bottlenecks of MSAPF. To solve MSAPF, we propose a novel and complete algorithm named Global Planning and Local Update (GPLU), which is a two-level algorithm and can efficiently find conflict-free paths for multi-size agents. GPLU is an unbounded sub-optimal algorithm that cannot find the optimal solution. However, we prove that GPLU is complete, which means that GPLU can return solutions for solvable MSAPF instances if such solutions exist. To improve the efficiency of GPLU, we propose two optimization strategies. The former improves efficiency while ensuring completeness, and the latter reduces the time complexity of GPLU to polynomial time. Extensive experiments conducted on a popular benchmark show that our proposed algorithms can support 20%$\sim$116.67% more multi-size agents than existing MAPF/MSAPF algorithms.

Recently, heterogeneous mobile robots (HMRs) have been widely implemented in warehouses or factories with limited space to improve efficiency. HMRs have different capabilities and sizes, which leads to two bottlenecks in the task planning for HMRs in an online environment. One is that it is hard to efficiently find high-quality task assignment results between heterogeneous tasks and HMRs because heterogeneous tasks need to be completed by HMRs of different capabilities. The other is that finding collision-free paths for HMRs of different sizes to complete assigned tasks is hard to satisfy the real-time demand. Existing works mainly consider solving these two bottlenecks separately while ignoring the mutual influence between the results of task assignment and collision-free path finding. To solve these issues, in this paper, we formally define the Online Task Planning with Collision Avoidance for HMRs (OTCH) problem, in which the platform aims to find the best task assignment and collision-free paths for HMRs to complete as many heterogeneous tasks as possible while minimizing the total cost containing the path cost and the delay cost. To solve the OTCH problem, we propose a novel task planning framework that considers task assignment and collision-free path finding simultaneously. Within this framework, we first present an aggregation algorithm to accelerate calculations. Then, we propose a network-flow-based task assignment algorithm to find a high-quality task assignment between heterogeneous tasks and HMRs in each batch. Finally, we propose a novel and efficient path finding algorithm to find collision-free paths for HMRs to complete assigned tasks while satisfying real-time demand. In addition, we not only analyze the complexity of the OTCH problem in detail but also give theoretical analysis for our proposed algorithms. Extensive experiments in a real-world dataset and two simulated datasets show that our proposed algorithms outperform the state-of-the-art while having the best scalability.