Search

Given a graph G , we call a partition ( V 1 , V 2 , … , V k ) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k ≥ 3 and has a polynomial time algorithm for each k ≤ 2 . (2) It is NP-hard to approximate the minimum induced star partition size within n 1 2 − ϵ for all ϵ > 0 . (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K 1 , r -free graphs, r ≥ 3 ), K 1 , 5 -free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r 2 -approximation algorithm for K 1 , r -free graphs ( r ≥ 2 ) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature.

The maturity in information technology and new energy technologies enables participants to generate, buy, and sell energy in energy trading systems. Although applying blockchain technology to energy trading has solved some drawbacks in traditional centralized energy systems, the openness and transparency characteristics make the trading records stored on the blockchain vulnerable to data-mining attacks that may cause indispensable privacy leakage. Due to high efficiency and low overhead, noise-addition is an appropriate solution for privacy preservation. Nonetheless, recent research on noise-addition needs to generate massive accounts, which brings a certain amount of waste and inconvenience for later regulation and management. To avoid the aforementioned issues, this paper proposes a consortium blockchain-enabled scheme to ensure the privacy of data stored on the blockchain and resist linking attacks initiated by data mining algorithms. Our scheme utilizes a dynamic partition algorithm to leverage an account mapping algorithm and a virtual token algorithm. Specifically, the account mapping algorithm utilizes a dynamic account allocation method to hide the trading distribution of active users. Furthermore, the virtual token algorithm applies Laplace noise to hide the actual energy consumption of inactive users and curb excessive accounts generation. Finally, we formally demonstrate the privacy and effectiveness of our proposed scheme in security analysis and experiment evaluations.

Decoding the real structure from the Social Internet of Things (SIoT) network with large-scale noise structure plays a fundamental role in data mining. Protecting private information from leakage in the mining process and obtaining accurate mining results is a significant challenge. To tackle this issue, we present a graph clustering privacy-preserving method based on structure entropy, which combines data mining with structural information theory. Specially, user private information in SIoT is encrypted by Brakerski-Gentry-Vaikuntanathan (BGV) homomorphism to generate a graph structure in ciphertext state, the ciphertext graph structure is then divided into different modules by applying two-dimensional structural information solution algorithm and entropy reduction principle node module partition algorithm, and the K-dimensional structural information solution algorithm is utilized to further cluster the internal nodes of the partition module. Moreover, normalized structural information and network node partition similarity are introduced to analyze the correctness and similarity degree of clustering results. Finally, security analysis and theoretical analysis indicate that this scheme not only guarantees the correctness of the clustering results, but also improves the security of private information in SIoT. Experimental evaluation and analysis shows that the clustering results of this scheme have higher efficiency and reliability.

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p$, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes $G$ colourful and the Colourful Partition problem asks whether there exists a partition of $G$ into at most $p$ colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on $k$-caterpillars, which are trees with a central path $P$ such that every vertex not in $P$ is within distance $k$ from a vertex in $P$. We prove that Colourful Components and Colourful Partition are NP-complete on $4$-caterpillars with maximum degree $3$, $3$-caterpillars with maximum degree $4$ and $2$-caterpillars with maximum degree $5$. On the other hand, we show that the problems are linear-time solvable on $1$-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree $d$ if $d \leq 2$ (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on $k$-caterpillars if $k \leq 1$, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on $k$-caterpillars, for every non-negative integer $k$, with respect to the maximum degree. We also show that Colourful Components is NP-complete on $5$-coloured planar graphs with maximum degree $4$ and on $12$-coloured planar graphs with maximum degree $3$. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019].

Volume segmentation based on surface attributes is an essential problem in multi-material fabrication and model packing. In practice, current mainstream fabrication techniques have difficulties in yielding models with diverse surface attributes in one pass owing to their craft limitations, making model segmentation a sensible choice for model realization. Partitioning 3D objects into single-attribute volumetric parts prevents fabricating models with different material in a single printing procedure, whereas the arisen challenge is to determine a reliable segmentation solution that is able to handle complicated models in various use scenarios. To achieve this goal, we propose a novel volume partition algorithm generating feasible volumetric parts, each of which is affiliated with one single surface attribute. Our technique enables model segmentation with least conflict and constrained wall thickness so that each volumetric segment can be realized independently by 3D-printing. Generally, it starts with computing a partition proposal guided by radial-based-function iso-surface, then optimizes segmentation interface with a prescribed minimal printing thickness to produce high-quality surface for every volumetric part, and finally splits unextractable volumetric parts into smaller sub-volumes to ensure assemblability of the whole model. As previous methods do not work well in optimizing segment interface for printing, we propose a differential evolution based smoothing algorithm to generate smooth and continuous interface, declining the risk of collision between adjacent volumetric parts. Extensive experimental results are provided in this paper to demonstrate the effectiveness and quality of our proposed technique, showing its advantages on model manufacture over prior methods.

In the past, many researchers used sliding-window mechanism in Internet of Things (IoT) data stream mining, which can divide the incoming large volume data into small segments and improve the information processing rate. With the emergence of heterogeneous IoT data streams, data forms become richer and more diverse. The fusion analysis of multimodality information can improve the accuracy of information processing and network decision-making, because it can make up for the lack of some information in a single-mode data stream. However, the representation of information in different data sources is different, and the amount of information contained in it is distinct. Thus, a weighted adaptive partition algorithm is proposed in this article, which performs a dynamic weighted fusion of multisource heterogeneous IoT data in sliding windows. The article adopts the Gaussian mixture model (GMM) to adaptively determine the weights of each data source, which is calculated based on the judgement confidence of each modal data to the change in data stream. Besides, the probability distribution change detection mechanism based on multimodality restricted Boltzmann machine (multimodality RBM) is proposed, which measures the joint probability distribution by the weighted data’s energy value. Finally, according to the energy change rate of the data stream, the size of the window is adjusted adaptively to realize the partition for heterogeneous IoT data stream. The algorithm proposed in this article is verified on the CUAVE data set and the analysis of results shows that the data under adaptive weighted fusion has better performance.

A real symmetric matrix A is copositive if $$x^\top Ax\ge 0$$ x ⊤ A x ≥ 0 for all $$x\ge 0$$ x ≥ 0 . As A is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015), are based upon the creation of increasingly fine simplicial partitions of simplices, testing for copositivity on each. We present a variant that decomposes a simplex $$\bigtriangleup $$ △ , say with n vertices, into a simplex $$\bigtriangleup _1$$ △ 1 and a polyhedron $$\varOmega _1$$ Ω 1 ; and then partitions $$\varOmega _1$$ Ω 1 into a set of at most $$(n-1)$$ ( n - 1 ) simplices. We show that if A is copositive on $$\varOmega _1$$ Ω 1 then A is copositive on $$\bigtriangleup _1$$ △ 1 , allowing us to remove $$\bigtriangleup _1$$ △ 1 from further consideration. Numerical results from examples that arise from the maximum clique problem show a significant reduction in the time needed to establish copositivity of matrices.

Calculating the “distance” between two given objects with respect to a designated “editing” operation is a hot research area in bioinformatics, where the “distance” is always defined as the minimum number of the “editing” operations required to transform one object into the other one. One of the famous problems in the area is the Minimum Common String Partition problem, which is the simplified variant of the Minimum Tree Cut/Paste Distance problem. Within the paper, we consider another simplified variant of the Minimum Tree Cut/Paste Distance problem, named Tree Assembly problem, of which the edge-deletion operations are specified. More specifically, the Tree Assembly problem aims to transform a given forest into a given tree by edge-addition operations only. In our investigations, we present a fixed-parameter algorithm with runtime 2 O ( k log ⁡ k ) n O ( 1 ) for the Tree Assembly problem, where k is the number of trees in the given forest, and n is the number of nodes in the given tree and forest. Additionally, we give a polynomial time algorithm for a restricted variant of the problem.

This work addresses the balanced connected k -partition problem ( BCP k ), which is formally defined as follows. Given a connected graph G = ( V , E ) with nonnegative weights on the vertices, find a partition { V i } i = 1 k of V such that each class V i induces a connected subgraph of G , and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP -hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of k or special classes of graphs, and inapproximability results. On the practical side, BCP k is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose three linear programming formulations for BCP k . The first one contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. The other two formulations are based on flows and have a polynomial number of constraints and variables. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other exact approaches presented in the literature.

Graph partitioning has been studied in the discipline between computer science and applied mathematics. It is a technique to distribute the whole graph data as a disjoint subset to a different device. The minimum graph partition problem with respect to an independence system of a graph has been studied in this paper. The considered independence system consists of one of the independent sets defined by Boutin. We solve the minimum partition problem in path graphs, cycle graphs, and wheel graphs. We supply a relation of twin vertices of a graph with its independence system. We see that a maximal independent set is not always a minimal set in some situations. We also provide realizations about the maximum cardinality of a minimum partition of the independence system. Furthermore, we study the comparison of the metric dimension problem of a graph with the minimum partition problem of that graph.

Most of today's smart grids are highly vulnerable to cascading failure attacks in which the failure of one or more critical components may trigger the sequential failure of other components, resulting in the eventual breakdown of the whole system. Existing works design different ranking methods for critical node or link identifications that fail to identify potential cascading failure attacks. In this work, we first consider the system from the attacker's point of view with a limited attack budget to study the smart grid vulnerability, referred to as Maximum-Impact through Critical-Line with Limited Budget (MICLLB) problem. We propose an efficient algorithm by considering the interdependency property of the system, called Greedy Based Partition Algorithm (GBPA) to solve the MICLLB problem. In addition, we design an algorithm, namely Homogeneous-Equality Based Defense Algorithm (HEBDA) to help reduce damages in case the system is suffering from the cascading failure attacks. Through rigorous theoretical analysis and experimentation, we demonstrate that the investigated problem is NP-complete problem and our proposed methods perform well within reasonable bounds of computational complexity.

Aim: The main motive of this study is to perform Adaptive Multi Rate Wideband (AMR-WB) Speech Steganography in network security to produce the stego speech with less loss of quality while increasing embedding capacities. Materials and Methods: TIMIT Acoustic-Phonetic Continuous Speech Corpus dataset consists of about 16000 speech samples out of which 1000 samples are taken and 80% pretest power for analyzing the speech steganography. AMR-WB Speech steganography is performed by Diameter Neighbor codebook partition algorithm (Group 1) and Neighbor Index Division codebook division algorithm (Group 2). Results: The AMR-WB speech steganography using DN codebook partition obtained average quality rate of 2.8893 and NID codebook division algorithm obtained average quality rate of 2.4196 in the range of 300bps embedding capacity. Conclusion: The outcomes of this study proves that the decrease in quality in NID is twice more than the DN based steganography while increasing the embedding capacities.

D2D communications are treated as potential services to achieve data re-transmissions among multicast vehicle-to-vehicle communications within one cluster, which can be used to improve the performance in vehicular ad hoc networks (VANETs). In this paper, we investigate the problem of resource utilization with D2D communications based on vehicles dynamic change characteristics in one cluster to maximize the ratio of spectral efficiency to transmission power for data re-transmissions. Firstly, given the transmission resources for intra-cluster D2D communications, a continuous time Markov chain model is established to capture the dynamic change characteristics of vehicles in intra-cluster, which is related to the change in number of allocated resources. And then, based on each intra-cluster steady state of the probability model, we design an adaptive re-transmitters selection approach in the cluster to solve the maximization problem that is a combinational programming problem with fractional objective. In this approach, a sub-cluster partition algorithm is proposed to optimize resource utilization in D2D re-transmissions. Besides these, the cooperative communication scheme is combined with the proposed approach to further enhance performance by selecting relays reasonably in different sub-clusters. By simulations, we evaluate the performance of the proposed approach (with or without cooperative communication) and the D2D retransmissions approach with one fixed re-transmitter which serves as a benchmark. The results show that the proposed approach with cooperative communication achieves a significant performance enhancement about average retransmission performance.

In the parallel computing framework of Hadoop/Spark, data skew is a common problem resulting in performance degradation, such as prolonging of the entire execution time and idle resources. What lies behind this issue is the partition imbalance, that causes significant differences in the amount of data processed by each reduce task. This paper proposes a key reassigning and splitting partition algorithm (SKRSP) to solve the partition skew from the source codes of Spark-core_2.11 project, which considers both the partition balance of the intermediate data and the partition balance after shuffle operators. First, we propose a step-based algorithm for sampling the input data to estimate the general key distribution of entire intermediate data. According to the types of the specific applications, we design two algorithms: hash based key reassigning algorithm (KRHP) and rang based key splitting algorithm (KSRP), which can generate appropriate strategy and implement the skew mitigation in shuffle phase. KKSRP generates the weighted bounds to split intermediate data for the type of sort-based applications while KRHP records these reassigned keys and the new reducers these keys belong to for other applications. Finally, we implement SKRSP in Spark 2.2.0 and evaluate its performance through four benchmarks exhibiting significant data skew: WordCount , Sort , Join , and PageRank . The experimental results verify that our algorithm not only can achieve a better partition balance but also reduce the execution time of reduce tasks effectively.

Testing provides essential information for managing infectious disease outbreaks, such as the COVID‐19 pandemic. When testing resources are scarce, an important managerial decision is who to test. This decision is compounded by the fact that potential testing subjects are heterogeneous in multiple dimensions that are important to consider, including their likelihood of being disease‐positive, and how much potential harm would be averted through testing and the subsequent interventions. To increase testing coverage, pooled testing can be utilized, but this comes at a cost of increased false‐negatives when the test is imperfect. Then, the decision problem is to partition the heterogeneous testing population into three mutually exclusive sets: those to be individually tested, those to be pool tested, and those not to be tested. Additionally, the subjects to be pool tested must be further partitioned into testing pools, potentially containing different numbers of subjects. The objectives include the minimization of harm (through detection and mitigation) or maximization of testing coverage. We develop data‐driven optimization models and algorithms to design pooled testing strategies, and show, via a COVID‐19 contact tracing case study, that the proposed testing strategies can substantially outperform the current practice used for COVID‐19 contact tracing (individually testing those contacts with symptoms). Our results demonstrate the substantial benefits of optimizing the testing design, while considering the multiple dimensions of population heterogeneity and the limited testing capacity.