In the Cluster Editing problem, sometimes known as (unweighted) Correlation Clustering, we must insert and delete a minimum number of edges to achieve a graph in which every connected component is a clique. Owing to its applications in computational biology, social network analysis, machine learning, and others, this problem has been widely studied for decades and is still undergoing active research. There exist several parameterized algorithms for general graphs, but little is known about the complexity of the problem on specific classes of graphs. Among the few important results in this direction, if only deletions are allowed, the problem can be solved in polynomial time on cographs, which are the P₄-free graphs. However, the complexity of the broader editing problem on cographs is still open. We show that even on a very restricted subclass of cographs, the problem is NP-hard, W[1]-hard when parameterized by the number p of desired clusters, and that time n^o(p/log p) is forbidden under the ETH. This shows that the editing variant is substantially harder than the deletion-only case, and that hardness holds for the many superclasses of cographs (including graphs of clique-width at most 2, perfect graphs, circle graphs, permutation graphs). On the other hand, we provide an almost tight upper bound of time n^O(p), which is a consequence of a more general n^O(cw⋅p) time algorithm, where cw is the clique-width. Given that forbidding P₄s maintains NP-hardness, we look at {P₄, C₄}-free graphs, also known as trivially perfect graphs, and provide a cubic-time algorithm for this class.

Point cloud registration (PCR) is a vital technique in photogrammetry and computer vision. It seeks to identify optimal spatial transformation parameters for adjacent point clouds. In contrast methods based on an initial estimate, PCR based on correspondence operates without the need for an initial guess. However, these correspondences, often established through feature descriptors, can contain a significantly high rate of outliers. Existing methods struggle to balance efficiency and precision effectively. This article, building on matches, constructs an undirected graph and proposes a strategy for preferred correspondences based on the maximum cliques (MC) of reliable edges, thereby selecting potential correspondences based on the reliable edges and MC. The registration challenge is then divided into two separate components: estimating rotation and translation. The rotation matrix is calculated utilizing the adaptive Maxwell–Boltzmann (AMB) algorithm, while the translation vector is derived from the median of the confidence interval (MCI). Comprehensive tests on both simulated and real registration datasets demonstrate that our approach excels in precise PCR, even with outlier rates above 99%. The source code will be available athttps://github.com/lixiaoyao0302/RoRO.

Point cloud registration is essential for constructing comprehensive geometric information of a scene. In feature-based point cloud registration, the extraction of stable features and accurate feature matching significantly enhance the algorithm’s robustness and overall effectiveness. This article introduces an automatic coarse registration method for large-scale urban point clouds utilizing line-planar semantic structural features (LSSFs), specifically designed for structured urban environments. The proposed method begins by extracting plane and line features from the point cloud and constructing LSSFs based on their geometric relationships. Then, it establishes correspondences between the source and target point clouds utilizing a hash table and the four line-planar spatial information constraints (FLSICs). The method then groups potential semantic features through a four-point geometric consistency (FPGC) approach, from which it selects the most reliable feature group to estimate the initial spatial transformation parameters. The registration result is further optimized through a global maximum consensus set (GMCS), achieving accurate registration of the point clouds. Experiments conducted on six large-scale urban point cloud datasets demonstrate the effectiveness of the proposed method in achieving pairwise point cloud registration, with a rotation error of merely 0.07° and a translation error of 0.11 m. In comparison to existing methods, this approach significantly enhances registration efficiency and accuracy, particularly when dealing with high-density point clouds and in the presence of noise. The method offers a reliable and efficient point cloud registration solution for complex urban environments, indicating potential for widespread application.

Structural graph parameters play an important role in parameterized complexity, including in kernelization. Notably, vertex cover, neighborhood diversity, twin-cover, and modular-width have been studied extensively in the last few years. However, there are many fundamental problems whose preprocessing complexity is not fully understood under these parameters. Indeed, the existence of polynomial kernels or polynomial Turing kernels for famous problems such as Clique, Chromatic Number, and Steiner Tree has only been established for a subset of structural parameters. In this work, we use several techniques to obtain a complete preprocessing complexity landscape for over a dozen of fundamental algorithmic problems.

For a graph class 𝒢, we define the 𝒢-modular cardinality of a graph G as the minimum size of a vertex partition of G into modules that each induces a graph in 𝒢. This generalizes other module-based graph parameters such as neighborhood diversity and iterated type partition. Moreover, if 𝒢 has bounded modular-width, the W[1]-hardness of a problem in 𝒢-modular cardinality implies hardness on modular-width, clique-width, and other related parameters. Several FPT algorithms based on modular partitions compute a solution table in each module, then combine each table into a global solution. This works well when each table has a succinct representation, but as we argue, when no such representation exists, the problem is typically W[1]-hard. We illustrate these ideas on the generic (α, β)-domination problem, which is a generalization of known domination problems such as Bounded Degree Deletion, k-Domination, and α-Domination. We show that for graph classes 𝒢 that require arbitrarily large solution tables, these problems are W[1]-hard in the 𝒢-modular cardinality, whereas they are fixed-parameter tractable when they admit succinct solution tables. This leads to several new positive and negative results for many domination problems parameterized by known and novel structural graph parameters such as clique-width, modular-width, and cluster-modular cardinality.

This paper deals with the adaptive nonlinear identification and trajectory tracking via dynamic multilayer neural network (NN) with different timescales. Two NN identifiers are proposed for nonlinear systems identification via dynamic NNs with different timescales including both fast and slow phenomenon. The first NN identifier uses the output signals from the actual system for the system identification. In the second NN identifier, all the output signals from nonlinear system are replaced with the state variables of the NNs. The online identification algorithms for both NN identifier parameters are proposed using Lyapunov function and singularly perturbed techniques. With the identified NN models, two indirect adaptive NN controllers for the nonlinear systems containing slow and fast dynamic processes are developed. For both developed adaptive NN controllers, the trajectory errors are analyzed and the stability of the systems is proved. Simulation results show that the controller based on the second identifier has better performance than that of the first identifier.

The members in the dynamic peer group (DPG) are divided into several clusters according to linker cluster architecture (J.B. Dennis and E. Anthony, 1981). In each cluster, the members perform the BD protocol (M. Burmester and Y. Desmedt, 1994) to establish the cluster key and the TGDH protocol (Y. Kim et al., 2004) is performed among the clusters to generate the group key. This method can not only avoid the weakness of AKA (auxiliary key agreement) of BD, but also reduce the computation cost of TGDH scheme. In our scheme the members have been authenticated based identity, and we prove the security in random oracle model.

The most popular approach to comparing two given tropical cyclones (TCs) is to measure the distance between various contour points of the TC extracted from a satellite image. However, this measure has a very high computational cost as it involves many point-to-point calculations. Moreover, this measure does not reflect the most distinctive features of a tropical cyclone, their spiral shape. In this paper, we propose the use of angle features and time warping for TC forecast. The gradient vector flow (GVF) snake model is applied to extract the contour points of a dominant tropical cyclone from the satellite image. Dvorak templates are used as references to predict the intensity of the tropical cyclone. Given two sets of contour points, one for each tropical cyclone, we retrieve the similarity of two shapes using angle features found among the successive contour points. We adopt a time warping approach to produce a fast and accurate result. Experimental results have shown that our approach is better than other conventional comparison approaches such as Hausdorff distance measure.