Search

This paper is concerned with designing algorithms for and analyzing the computational complexity of the partial vertex cover problem in trees. Graphs (and trees) are frequently used to model risk management in various systems. In particular, Caskurlu et al. in [4] have considered a system which essentially represents a tripartite graph. The goal in this model is to reduce the risk in the system below a predefined risk threshold level. It can be shown that the main goal in this risk management system can be formulated as a Partial Vertex Cover problem on bipartite graphs. In this paper, we focus on a special case of the partial vertex cover problem, when the input graph is a tree. We consider four possible versions of this setting, depending on whether or not, the vertices and edges are weighted. Two of these versions, where edges are assumed to be unweighted, are known to be polynomial-time solvable. However, the computational complexity of this problem with weighted edges, and possibly with weighted vertices, remained open. The main contribution of this paper is to resolve these questions by fully characterizing which variants of partial vertex cover remain NP-hard in trees, and which can be solved in polynomial time. In the paper, we propose two pseudo-polynomial DP-based algorithms for the most general case in which weights are present on both the edges and the vertices of the tree. One of these algorithms leads to a polynomial-time procedure, when weights are confined to the edges of the tree. The insights used in this algorithm are combined with additional scaling ideas to derive an FPTAS for the general case. A secondary contribution of this work is to propose a novel way of using centroid decompositions in trees, which could be useful in other settings as well. [ABSTRACT FROM AUTHOR]

Distributed learning has attracted considerable attention in recent years due to its power to deal with big data in various science and engineering problems. Based on a divide-and-conquer strategy, this paper studies the distributed robust regression algorithm associated with correntropy losses and coefficient regularization in the scheme of kernel networks, where the kernel functions are not required to be symmetric or positive semi-definite. We establish explicit convergence results of such distributed algorithm depending on the number of data partitions, robustness and regularization parameters. We show that with suitable parameter choices the distributed robust algorithm can obtain the optimal convergence rate in the minimax sense, and simultaneously reduce the computational complexity and memory requirement in the standard (non-distributed) algorithms. [ABSTRACT FROM AUTHOR]

Mathematical morphology and convolution operators are two different methods to extract the characteristics and structures of images. Over the past decades, Deep Convolutional Neural Networks (DCNN) have been proven to be more powerful than traditional image-processing approaches. In this paper, we propose a novel structure called Deep Hybrid Neural Network (DHNN) by taking advantage of the convolution and morphological neural layers. Its practical application to polyp detection in medical images is illustrated. For experimental completeness, we adopt nine polyp image datasets, including publicly available data and our own collected data. For performance comparisons, we select three backbone models. Experimental results show that our DHNN achieves the best performance in comparisons in terms of computational complexity and accurate performance. [ABSTRACT FROM AUTHOR]

With the rapid development of deep learning technology, object detection algorithms have made significant breakthroughs in the field of computer vision. However, due to the complexity and computational requirements of deep Convolutional Neural Network (CNN), these models face many challenges in practical applications, especially on resource-constrained edge devices. To address this problem, researchers have proposed many lightweight methods that aim to reduce the model size and computational complexity while maintaining high performance. The popularity of mobile devices and embedded systems has led to an increasing demand for lightweight models. However, existing lightweight methods often lead to accuracy loss, limiting their feasibility in practical applications. Therefore, how to realize the light weight of the model while maintaining high accuracy has become an urgent problem to be solved. To address this challenge, this paper proposes a lightweight YOLOv7 method based on PConv, Squeeze-and-Excitation (SE) attention mechanism and Wise-IoU (WIoU), which we refer to as YOLOv7-PSW. PConv can effectively reduce the number of parameters and computational complexity. The SE can help the model focus on important feature information, thereby improving performance. WIoU is introduced to measure the similarity between the detection box and the Ground Truth, so that the model can effectively reduce the False Positive rate. By applying these advanced techniques to the YOLOv7, we achieve a lightweight model while maintaining a high detection accuracy. Experimental results on PASCAL VOC dataset show that YOLOv7-PSW performs better than the original YOLOv7 on object detection tasks. The number of parameters is reduced by 12.3%, FLOPs is reduced by 18.86%, and the accuracy is improved by about 0.5%. While the detection accuracy is not decreased or even slightly improved, the number of FLOPs and parameters is greatly reduced, which realizes lightweight to a certain extent. The proposed method can provide new ideas and directions for the subsequent research on lightweight object detection, and is expected to promote its application on edge devices. Meanwhile, YOLOv7-PSW can also be applied to other computer vision tasks to improve its performance and efficiency. In summary, the proposed YOLOv7-PSW lightweight method realizes the light weight of the model while maintaining high accuracy. This is of great significance for promoting the application of object detection algorithms on edge devices. [ABSTRACT FROM AUTHOR]

In this paper, we present two new graph structures that can be used to model information routing in heterogeneous communication networks. These are cardinality-constrained graphs (CCGs) and interval-constrained graphs (ICGs). In both cardinality- and interval-constrained graphs, the nodes in the graph are labeled. In a CCG, each label is associated with an upper bound. A path in a CCG is considered valid, if the number of nodes on the path with any particular label is at most the upper bound associated with that label. In an ICG, each label is associated with both an upper bound and a lower bound. A path in an ICG is considered valid, if the number of nodes on the path with any particular label is between the upper and lower bounds associated with that label. In this paper, we examine the computational complexities of finding valid paths in both CCGs and ICGs. In particular, we show that these problems are NP-hard. Additionally, we propose novel algorithms for finding paths in CCGs and a subset of ICGs. We also demonstrate the effectiveness of our algorithms on CCGs and ICGs of various sizes. The past decade has seen a surge in the degree of hardware-heterogeneous device interconnectivity, Additionally, there has been a proliferation of resource-constrained wireless sensor networks. Thus, the problems of finding valid paths in CCGs and ICGs are of interest. Nodes in wireless sensor networks can be faulty, vulnerable, energy-constrained, or untrusted. These nodes may also have differing degrees of performance or power efficiency. This can pose a significant challenge in routing the flow of information between nodes. The heterogeneity of nodes in such networks is captured through the use of CCGs and ICGs. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper vertex coloring with a domination property that each vertex dominates a color class. The minimum number of colors used in a dominator coloring of G is called dominator chromatic number of G and is denoted as χ d (G). Graphs with χ d (G) ≤ 3 have characterizations and such graphs can be recognized in polynomial time. However, for k ≥ 4 , deciding whether χ d (G) ≤ k is NP-hard. In this paper, we investigate the computational complexity of minimum q -dominator partization problem (Min- q -D-Partz). In Min- q -D-Partz, given a graph G , the objective is to find a vertex set S of minimum size such that χ d (G [ V ∖ S ]) ≤ q. We prove that Min- 2 -D-Partz is APX-complete and has a two-factor approximation algorithm. We also prove that Min- 3 -D-Partz cannot be approximated within any constant factor and can be approximated within a factor of O (log n). [ABSTRACT FROM AUTHOR]

Epilepsy is one kind of neurological disease characterized by recurring seizures. Recurrent seizures can cause ongoing negative mental and cognitive damage to the patient. Therefore, timely diagnosis and treatment of epilepsy are crucial for patients. Manual electroencephalography (EEG) signals analysis is time and energy consuming, making automatic detection using EEG signals particularly important. Many deep learning algorithms have thus been proposed to detect seizures. These methods rely on expensive and bulky hardware, which makes them unsuitable for deployment on devices with limited resources due to their high demands on computer resources. In this paper, we propose a novel lightweight neural network for seizure detection using pure convolutions, which is composed of inverted residual structure and multi-scale channel attention mechanism. Compared with other methods, our approach significantly reduces the computational complexity, making it possible to deploy on low-cost portable devices for seizures detection. We conduct experiments on the CHB-MIT dataset and achieves 98.7% accuracy, 98.3% sensitivity and 99.1% specificity with 2.68 M multiply-accumulate operations (MACs) and only 88 K parameters. [ABSTRACT FROM AUTHOR]

Chaotic systems are often considered to be a basis for various cryptographic methods due to their properties, which correspond to cryptographic properties like confusion, diffusion and algorithm (attack) complexity. In these kinds of applications, chaos robustness is desired. It can be defined by the absence of periodic windows and coexisting attractors in some neighborhoods of the parameter space. On the other hand, when used as a basis for neuromorphic modeling, chaos robustness is to be avoided, and the edge-of-chaos regime is needed. This paper analyses the robustness and edge-of-chaos for Chua's systems, comprising either a piecewise linear or a smooth function nonlinearity, using a novel figure of merit based on correlation coefficient and Lyapunov exponent. Calculation complexity, which is important when a chaotic system is implemented, is evaluated for double and decimal data types, where needed calculation time varies by a factor of about 1500, depending on the nonlinearity function and the data type. On the other hand, different data types result in different number precision, which has some practical advantages and drawbacks presented in the paper. [ABSTRACT FROM AUTHOR]

Nowadays, many sequences of events are generated in areas as diverse as healthcare, finance, and social network. People have been studying these data for a long time. They hope to predict the type and occurrence time of the next event by using relationships among events in the data. recently, with the successful application of Recurrent Neural Network (RNN) in natural language processing, it has been introduced into point process. However, RNN cannot capture the long-term dependence among events well, and self-attention can partially mitigate this problem precisely. Transformer Hawkes Process (THP) using self-attention greatly improves the performance of the Hawkes Process, but THP cannot ignore the effect of irrelevant events, which will affect the computational complexity and prediction accuracy of the model. In this paper, we propose an Adaptively Sparse Transformers Hawkes Process (ASTHP). ASTHP considers the periodicity and nonlinearity of event time in the time encoding process. The sparsity of the ASTHP is achieved by substituting Softmax with α -entmax: α -entmax is a differentiable generalization of Softmax that allows unrelated events to gain exact zero weight. By optimizing the neural network parameters, different attention heads can adaptively select sparse modes (from Softmax to Sparsemax). Compared with the existing models, ASTHP model not only ensures the prediction performance but also improves the interpretability of the model. For example, the accuracy of ASTHP model on MIMIC-II dataset is improved by nearly 3 percentage points, and the model fitting degree and stability are also improved significantly. [ABSTRACT FROM AUTHOR]

In Blind Hyperspectral Unmixing, the accuracy of the estimated number of endmembers affects the succeeding steps of extraction of endmember signatures and acquiring their fractional abundances. The characteristics of endmember signature depend on the nature of the material on the ground and share similar characteristics for variants of the same material. In this paper, we introduce a new concept of sub-endmembers to identify similar materials that are variants of a global endmember. Identifying the sub-endmembers will provide a meaningful interpretation of the endmember variability along with increased unmixing accuracy. This paper proposes a new algorithm exploiting both the spatial and spectral information present in hyperspectral data. The hyperspectral data are segmented into homogenous regions (superpixels) based on the Simple Linear Iterative Clustering (SLIC) algorithm, and the mean spectral of each region is accounted for in finding the global endmembers. The difference of eigenvalues-based thresholding method is used to find the number of global and sub-endmembers. The method has been tested on synthetic and real hyperspectral data and has successfully estimated the number of global endmembers as well as sub-endmembers. The method is also compared with other state-of-the-art methods, and better performances are obtained at a reasonably lower computational complexity. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel multi-threaded parallel permutation and channel-combined diffusion for image encryption which is independent of plain text. In our proposed method, the coupled map lattice is used to generate the key sequences for multi-thread permutation and diffusion. Then intra- and inter-thread permutations are achieved using multi-threading in combination with the tent mapping. For the subsequent diffusion, this paper introduces a method based on channel-combined diffusing which simultaneously diffuses three channels. Experimental results indicate a high encryption performance with the capability of effectively resisting the known plain text and differential attacks. Our proposed method also has a lower computational complexity which enables its applicability in practical scenarios. [ABSTRACT FROM AUTHOR]

In this paper, a criterion for efficient coupled-mode matrix calculation in a constant depth ocean with range-dependent sound–speed fluctuation is proposed. The usual stepwise coupled mode requires high computational power to calculate the mode-coupling matrix at each interface of the range segment. To reduce the computational complexity, the criterion for selecting appropriate mode pairs, which strongly affects the mode-coupling matrix, is derived from perturbation theory. This criterion determines the effective range of the modal beat wavenumber. Numerical examples indicate that compared with the full calculation of the mode-coupling matrix, for the calculation using the proposed criterion, the computational complexity is significantly reduced, while the accuracies of the mode-coupling matrix and acoustic field are maintained. [ABSTRACT FROM AUTHOR]

Existing Bayesian network (BN) structure learning algorithms based on dynamic programming have high computational complexity and are difficult to apply to large-scale networks. Therefore, this paper proposes a Dynamic Programming BN structure learning algorithm based on Mutual Information, the MIDP (Dynamic Programming Based on Mutual Information) algorithm. The algorithm uses mutual information to build the maximum spanning tree and M -order matrix, and introduces a penalty coefficient d based on the matrix-based node removal strategy, so as to reduce the number of scoring calculations and time consumption of the algorithm. Simulation results show that, compared with DP, SMDP and MEDP algorithms, the MIDP algorithm can reduce the calculation times and time consumption of algorithm scores while maintaining the accuracy of the algorithm when selecting the appropriate d value. [ABSTRACT FROM AUTHOR]

This paper will focus on linguistic constructions involving intensional emotive predicates in order to assess the computational complexity of such constructions based on the features of intensional elements in such constructions. It will be first shown that linguistic constructions vary as a function of the nature of intensional elements involved in such constructions. The important insights derived from these facts will be then carried forward for an exploration of the computational complexity of intensional emotive constructions which can be seen to co-vary in complexity scales with the number of intensional elements or features of intensional elements. Possible ramifications emanating from this for the cognitive tractability of semantic contents and for natural language processing will be offered at the end of the paper. [ABSTRACT FROM AUTHOR]

A shockwave signal has the characteristics of short duration and wide dynamic range, so the wireless test system needs to collect it at a continuous high sampling rate, resulting in a short node life cycle and a large amount of redundant data during the test process. Moreover, test data with confidentiality, if it is still recorded and transmitted in plaintext, will challenge information security. Therefore, a compressed and encrypted acquisition framework based on hyperchaotic compressed sensing and semi-tensor is proposed in this paper. Firstly, a new four-dimensional hyperchaotic system is used to generate a compressed sensing measurement matrix to improve the encryption and anti-noise performance. Secondly, for saving memory space and improving computing efficiency, the semi-tensor product is introduced to reduce the dimension of the measurement matrix exponentially. The experimental results show that the proposed framework can realize the compressed and encrypted acquisition of transient signals with small memory space and low computational complexity. And the acquisition results can be directly transmitted to meet the requirements of real-time wireless transmission bandwidth and information security. [ABSTRACT FROM AUTHOR]

Robust optimization problems have attracted considerable attention in recent years. In this paper, we focus on two fundamental robust optimization problems: SVM with outliers and k -center clustering with outliers. The key obstacle is that the outliers can be located arbitrarily in the space (e.g., by an attacker), and thus they are actually quite challenging combinatorial optimization problems. Their computational complexities can be very high especially in high dimensional spaces. The Johnson–Lindenstrauss (JL ) Transform is a popular random projection method for dimension reduction. Though the JL transform has been widely studied in the past decades, its effectiveness for dealing with high-dimensional optimizations with outliers has never been investigated before (to the best of our knowledge). Based on some novel insights from the geometry, we prove that the complexities of these two problems can be significantly reduced through the JL transform. Moreover, we prove that the solution in the dimensionality-reduced space can be efficiently recovered in the original ℝ d space while the quality is still preserved. To study its performance in practice, we compare different JL transform methods with several other well known dimension reduction methods in our experiments. [ABSTRACT FROM AUTHOR]

In this paper, Lagrangian-based method has been proposed for tuning the parameters of fractional order P I α D β controller. In this method, the five parameters ( K p , K i , K d , α and β) of fractional order P I α D β controller (FOPID) are suitably optimized, and successfully applied to a benchmark stable second-order feedback system. To prove the performance of the proposed method, several state-of-the-art approaches were compared. The computational complexity, robustness and stability analysis has been performed to investigate the performance of all these algorithms. Moreover, the precision and flexibility analysis among all these approaches has also been carried out in this paper. The closed loop response of the second-order bench mark stable plant in Simulink has also been depicted in this paper. [ABSTRACT FROM AUTHOR]

Let G = (V , E) be a connected graph. A function f : V → { 0 , 1 , 2 } is called a Roman dominating function if every vertex v with f (v) = 0 is adjacent to a vertex u with f (u) = 2. If further the set V 0 = { v : f (v) = 0 } is an independent set, then f is called an outer independent Roman dominating function (OIRDF). Let w (f) = ∑ v ∈ V f (v) and γ oiR (G) = min { w (f) : f  is an OIRDF of  G }. Then γ o i R (G) is called the outer independent Roman domination number of G. In this paper, we prove that the decision problem for γ o i R (G) is NP-complete for chordal graphs. We also show that γ o i R (G) is linear time solvable for threshold graphs and bounded tree width graphs. Moreover, we show that the domination and outer independent Roman domination problems are not equivalent in computational complexity aspects. [ABSTRACT FROM AUTHOR]

Graph attention networks (GATs)-based method performs well in Human–Object Interaction (HOI) detection due to its ability to aggregate contextual information. However, the traditional GATs-based methods are computationally intensive, and the graph's structure cannot effectively represent the HOI in an image. Meanwhile, the graph models are unable to predict the interactions that involve less contextual information correctly. In this paper, we design a method based on graph models called V-SGATs, which stands for Visual Branch and Star Graph Attention Networks. The human-centric star graph and object-centric star graph are adopted to reduce computational complexity, and the logical structure of the star graph can represent HOI more reasonably. Meanwhile, the visual branch that recognizes the interaction without utilizing the contextual information is designed to aid the graph model in predicting the interactions that involve less contextual information. Experiments are carried out on two large-scale HOI public benchmarks V-COCO and HICO-DET, and the results show that the proposed method performs better than most of the existing methods based on GATs. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 } which satisfies the following conditions is called a weakly connected Roman dominating function (WCRDF) of G with weight h (V) = ∑ p ∈ V h (p). (C1). For all q ∈ V with h (q) = 0 there exists a vertex r such that (q , r) ∈ E and h (r) = 2 and (C2). The graph with vertex set V (G) and edge set { (p , z) : h (p) ≥ 1 or h (z) ≥ 1 or both } is connected. The problem of determining WCRDF of minimum weight is called minimum weakly connected Roman domination problem (MWCRDP). In this paper, we show that MWCRDP is polynomial time solvable for bounded treewidth graphs, threshold graphs and chain graphs. We design a 2 (1 +) (1 + ln (Δ − 1)) -approximation algorithm for the MWCRDP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless P = N P. Next, we show that MWCRDP is APX-hard for graphs with Δ = 4. We also show that the domination and weakly connected Roman domination problems are not equivalent in computational complexity aspects. Finally, two different integer linear programming formulations for MWCRDP are proposed. [ABSTRACT FROM AUTHOR]

In video Super Resolution (SR), the problem of cost expense concerning the attainment of enhanced spatial resolution, computational complexity and difficulties in motion blur makes video SR a complex task. Moreover, maintaining temporal consistency is crucial to achieving an efficient and robust video SR model. This paper plans to develop an intelligent SR model for video frames. Initially, the video frames in RGB format will be transformed into HSV. In general, the improvement in video frames is done in V-channel to achieve High-Resolution (HR) videos. In order to enhance the RGB pixels, the current window size is enhanced to high-dimensional window size. As a novelty, this paper intends to formulate a high-dimensional matrix with enriched pixel intensity in V-channel to produce enhanced HR video frames. Estimating the enriched pixels in the high-dimensional matrix is complex, however in this paper, it is dealt in a significant way by means of a certain process: (i) motion estimation (ii) cubic spline interpolation and deblurring or sharpening. As the main contribution, the cubic spline interpolation process is enhanced via optimization in terms of selecting the optimal resolution factor and different cubic spline parameters. For optimal tuning, this paper introduces a new modified algorithm, which is the modification of the Rider Optimization Algorithm (ROA) named Mean Fitness-ROA (MF-ROA). Once the HR image is attained, it combines the HSV and converts to RGB, which obtains the enhanced output RGB video frame. Finally, the performance of the proposed work is compared over other state-of-the-art models with respect to BRISQUE, SDME and ESSIM measures, and proves its superiority over other models. [ABSTRACT FROM AUTHOR]

Quantum key distribution (QKD) allows authenticated parties to share secure keys. Its security comes from quantum physics rather than computational complexity. The previous work has been able to demonstrate the security of the BB84 protocol based on the uncertainty principle, entanglement purification and information theory. In the security proof method based on entanglement purification, it is assumed that the information of Calderbank–Shor–Steane (CSS) error correction code cannot be leaked, otherwise, it is insecure. However, there is no quantitative analysis of the relationship between the parameter of CSS code and the amount of information leaked. In the attack and defense strategy of the actual quantum key distribution system, especially in the application of the device that is easy to lose or out of control, it is necessary to assess the impact of the parameter leakage. In this paper, we derive the relationship between the leaked parameter of CSS code and the amount of the final key leakage based on the BB84 protocol. Based on this formula, we simulated the impact of different CSS code parameter leaks on the final key amount. Through the analysis of simulation results, the security of the BB84 protocol is inversely proportional to the value of n − k 1 and k 1 − k 2 in the case of the CSS code leak. [ABSTRACT FROM AUTHOR]

The three-level inverter is extensively preferred in medium-voltage industrial applications over the conventional inverter due to its benefits. The performance of inverter is better when the space vector modulation (SVM) approach is preferred. However, the implementation of conventional SVM approach is more complex. In this paper, a decomposition-based new SVM algorithm for three-level inverter is proposed to reduce computational complexity and implementation time using a low-cost digital controller. Initially, the performance of the proposed SVM algorithm is studied through MATLAB simulation using the conventional switching sequence 0127. Further enhancing the performance, the proposed algorithm is implemented with various advanced discontinuous SVPWM strategies using the advanced switching sequences of 1012–2721 and 0121–7212. The no-load motor current THD and switching loss analysis for ADSVPWM and conventional SVPWM strategies at different modulation indices are presented is this paper for a comparison point of view. The no load motor current THD results obtained through simulation are validated experimentally by implementing the proposed algorithm on real-time interface tool through dSPACE, which is used to control constant V/F-controlled three-level inverter-fed induction motor. Further to show the effectiveness of the proposed technique, the experimental investigation is done on induction motor at loaded condition and the results are presented. [ABSTRACT FROM AUTHOR]

One way to understand the network function and analyze the network structure is to find the communities of the network accurately. Now, there are many works about designing algorithms for community detection. Most community detection algorithms are based on modularity optimization. However, these methods not only have disadvantages in computational complexity, but also have the problem of resolution restriction. Designing a community detection algorithm that is fast and effective remains a challenge in the field. We attempt to solve the community detection problem in a new perspective in this paper, believing that the assumption used to solve the link prediction problem is useful for the problem of community detection. By using the similarity between modules of the network, we propose a new method to extract the community structure in this paper. Our algorithm consists of three steps. First, we initialize a community partition based on the distribution of the node degree; second, we calculate the similarity between different communities, where the similarity is the index to describe the closeness of the different communities. We assume that the much closer the two different communities are, the greater the likelihood of being divided together; finally, merge the pairs of communities which has the highest similarity value as possible as we can and stop when the condition is not satisfied. Because the convergence of our algorithm is very fast in the process of merging, we find that our method has advantages both in the computational complexity and in the accuracy when compared with other six classical algorithms. Moreover, we design a new measure to describe how difficulty the network division is. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) is a modern technology that is applicable almost everywhere nowadays. Everything is connected to the Internet in the modern digital era. IoT is a collection of things that are interconnected to share information. Devices connected to IoT networks have some limitations in performing heavy computational tasks because of the availability of less computational and battery power. Attribute Based Encryption (ABE) is a modern public-key cryptographic technique that provides privacy with access control. The bilinear map is an expensive operation that is used in most of the ABE schemes. Elliptic Curve Cryptography (ECC) is an alternative for bilinear pairing to reduce the computation of encryption and decryption in ABE schemes. The process of encryption and decryption of ABE is a heavy computational task for resource-constrained devices. In this paper, an outsourcing-based decryption of ABE using ECC is proposed to reduce the decryption overhead of devices that have limited computational resources. Our scheme divides the computation of the decryption of ABE into two stages: first, the partial decryption of ciphertext in the cloud server, and second, the final decryption of partially decrypted ciphertext by the data user to retrieve the original message. This scheme is secure against the malicious cloud server by adding a blinding factor into the secret to be shared. The blinding factor is shared with intended users through attribute authority. The experimental results demonstrate that our scheme can reduce the decryption complexity and save the computational time of devices, compared to the existing schemes. Thus the proposed scheme is applicable for lightweight devices used in IoT. [ABSTRACT FROM AUTHOR]

Convolutional neural networks (CNNs) have emerged as a prominent choice in artificial intelligence tasks. Recent advancements in CNN designs have greatly improved the performance and energy-efficiency of several computation-intensive applications. However, in real-time applications, greater accuracy of CNN is attained at the expense of very high computational cost and complexity. Further, the implementation of real-time CNN on embedded platforms is highly challenging due to resource and power constraints. This paper addresses the aforesaid computational complexity and presents an accelerator architecture accompanied by a novel kernel design to improve overall CNN performance. The proposed kernel design introduces a computing mechanism that reduces the data movement cost in terms of computational cycle count (latency) by parallelizing the convolution processing elements. This architecture takes advantage of the overlap of spatially adjacent data. The performance of the proposed architecture is also analyzed for multiple hyper-parameter configurations. The proposed accelerator achieves an average of 1 6 × improvement in reduction of execution time than the conventional computing architecture. To analyze the proposed architecture's performance, we validate the architecture with AlexNet and VGG-16 CNN models. The proposed accelerator architecture achieves an average of 1. 7 × throughput improvement over state-of-the-art accelerators. [ABSTRACT FROM AUTHOR]

For a simple, undirected, connected graph G , a function h : V (G) → { 0 , 1 , 2 , 3 } which satisfies the following conditions is called a total Roman {3}-dominating function (TR3DF) of G with weight h (V) = ∑ p ∈ V h (p) : (C1) For every vertex u ∈ V if h (u) = 0 , then u has m (m ≥ 1) neighbors such that whose sum is at least 3, and if h (u) = 1 , then u has n (n ≥ 1) neighbors such that whose sum is at least 2. (C2) The subgraph induced by the set of vertices labeled one, two or three has no isolated vertices. For a graph G , the smallest possible weight of a TR3DF of G denoted γ t { R 3 } (G) is known as the total Roman { 3 } -domination number of G. The problem of determining γ t { R 3 } (G) of a graph G is called minimum total Roman {3}-domination problem (MTR3DP). In this paper, we show that the problem of deciding if G has a TR3DF of weight at most l for chordal graphs is NP-complete. We also show that MTR3DP is polynomial time solvable for bounded treewidth graphs, chain graphs and threshold graphs. We design a 3 (ln (Δ − 0. 5) + 1. 5) -approximation algorithm for the MTR3DP and show that the same cannot have (1 − δ) ln | V | ratio approximation algorithm for any δ > 0 unless NP ⊆ DTIME (| V | O (log log | V |)). Next, we show that MTR3DP is APX-complete for graphs with Δ = 4. We also show that the domination and total Roman {3}-domination problems are not equivalent in computational complexity aspects. Finally, we present an integer linear programming formulation for MTR3DP. [ABSTRACT FROM AUTHOR]

In this paper, we propose a sparse tensor regression model for multi-view feature selection. Apart from the most of existing methods, our model adopts a tensor structure to represent multi-view data, which aims to explore their underlying high-order correlations. Based on this tensor structure, our model can effectively select the meaningful feature set for each view. We also develop an iterative optimization algorithm to solve our model, together with analysis about the convergence and computational complexity. Experimental results on several popular multi-view data sets confirm the effectiveness of our model. [ABSTRACT FROM AUTHOR]

For a formal language L , the problem of language enumeration asks to compute the length-lexicographically smallest word in L larger than a given input w ∈ Σ ∗ (henceforth called the L -successor of w). We investigate this problem for regular languages from a computational complexity and state complexity perspective. We first show that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are (in general) necessary and sufficient for an unambiguous finite-state transducer to compute L -successors. As a byproduct, we obtain that if L is recognized by a DFA with n states, then 2 Θ (n log n) states are sufficient for a DFA to recognize the subset S (L) of L composed of its lexicographically smallest words. We give a matching lower bound that holds even if S (L) is represented as an NFA. It has been known that L -successors can be computed in polynomial time, even if the regular language is given as part of the input (assuming a suitable representation of the language, such as a DFA). In this paper, we refine this result in multiple directions. We show that if the regular language is given as part of the input and encoded as a DFA, the problem is in N L. If the regular language L is fixed, we prove that the enumeration problem of the language is reducible to deciding membership to the Myhill-Nerode equivalence classes of L under D L O G T I M E -uniform A C 0 reductions. In particular, this implies that fixed star-free languages can be enumerated in A C 0 , arbitrary fixed regular languages can be enumerated in N C 1 and that there exist regular languages for which the problem is N C 1 -complete. [ABSTRACT FROM AUTHOR]

Identifying critical nodes in complex networks has gained increasing attention in recent years. However, how to design an algorithm that has low computational complexity but can accurately identify important network nodes is still a challenge. Considering the role of structural holes in shaping communication channels, this paper presents an effective method based on local characteristics to identify critical nodes that play important roles in maintaining network connectivity. Our method considers the connections of a node as well as the connectivity of the neighborhood of the node. Through numerical simulations on various real-world networks, we have demonstrated that the proposed approach outperforms some other well-known heuristic algorithms in identifying vital nodes and leads to faster network collapse in target destruction. [ABSTRACT FROM AUTHOR]

EMG signal-based pattern recognition (EMG-PR) techniques have gained lots of focus to develop myoelectric prosthesis. The performance of the prosthesis control-based applications mainly depends on extraction of eminent features with minimum neural information loss. The machine learning algorithms have a significant role to play for the development of Intelligent upper-limb prosthetic control (iULP) using EMG signal. This paper proposes a new technique of extracting the features known as advanced time derivative moments (ATDM) for effective pattern recognition of amputees. Four heterogeneous datasets have been used for testing and validation of the proposed technique. Out of the four datasets, three datasets have been taken from the standard NinaPro database and the fourth dataset comprises data collected from three amputees. The efficiency of ATDM features is examined with the help of Davies–Bouldin (DB) index for separability, classification accuracy and computational complexity. Further, it has been compared with similar work and the results reveal that ATDM features have excellent classification accuracy of 98.32% with relatively lower time complexity. The lower values of DB criteria prove the good separation of features belonging to various classes. The results are carried out on 2.6 GHz Intel core i7 processor with MATLAB 2015a platform. [ABSTRACT FROM AUTHOR]

Prolonging the lifetime of wireless sensor networks (WSN) is the biggest challenging issue. In wireless multimedia sensor networks (WMSNs), sensor nodes have limited energy resource and to increase the lifetime of the network, it is necessary to design an effective fast algorithm that aims at reducing the consumed power. This paper proposes an energy-efficient discrete cosine transform (DCT) approximation requiring only 12 additions. Associated with a JPEG compression chain, this DCT approximation ensures a very good rate-distortion compromise, but above all, a very low computational complexity and significant compatibility with the exact DCT. Simulation results clearly show that the proposed fast transform algorithm achieves a better trade-off between image quality, computational complexity and energy consumption compared to any existing pruned DCT approximations. Furthermore, it is very suitable for the resource constrained wireless visual sensor networks (WVSNs) requiring low bitrates. [ABSTRACT FROM AUTHOR]

The state-of-the-art physics alliances have augmented various opportunities to solve complex real-world problems. These problems require both multi-disciplinary expertise as well as large-scale computational experiments. Therefore, the physics community needs a flexible platform which can handle computational challenges such as volume of data, platform heterogeneity, application complexity, etc. Cloud computing provides an incredible amount of resources for scientific users on-demand, thus, it has become a potential platform for executing scientific applications. To manage the resources of Cloud efficiently, it is required to explore the resource prediction and scheduling techniques for scientific applications which can be deployed on Cloud. This paper discusses an extensive analysis of scientific applications, resource predictions and scheduling techniques for Cloud computing environment. Further, the trend of resource prediction-based scheduling and the existing techniques have also been studied. This paper would be helpful for the readers to explore the significance of resource prediction-based scheduling techniques for physics-based scientific applications along with the associated challenges. [ABSTRACT FROM AUTHOR]

Complex networks depict the individual relationship in a population, which can help to deeply mine the characteristics of complex networks and predict the potential collaboration between individuals by analyzing their interaction within different groups or clusters. However, the existing algorithms are with high complexity, which cost much computational time. In this paper, an efficient graph clustering algorithm based on spectral coarsening is proposed, to deal with the large time complexity of the traditional spectral algorithm. We first find the subset most possibly belonged to the same cluster in the original network, and merge them into a single node. The scale of the network will decrease with the network being coarsened. Then, the spectral clustering algorithm is performed on the coarsened network with the maintained advantages and the improved time efficiency. Finally, the experimental results on the multiple datasets demonstrate that the proposed algorithm, compared with the current state-of-the-art methods, has superior performance. [ABSTRACT FROM AUTHOR]

This paper proposes an image encryption technique which is fast and secure. The encryption scheme is designed for secure transmission of video surveillance data (keyframes) over insecure network. The image encryption technique employs 1D Sine–Sine system with better chaotic properties than its seed map and faster than higher-dimensional chaotic systems. Further, design of encryption scheme is based on two permutation rounds, which employs pixel swapping operation and diffusion operation which is simple and provides required security against plaintext, differential and various other attacks. Three separate chaotic sequences are generated using 1D Sine–Sine system which enhances the key space of the encryption scheme. Secret keys are updated dynamically with SHA-256 hash value obtained from plain image. Hash values of plain image are efficiently used without loss of any hash value information. This makes the encryption scheme plaintext sensitive and secure against plaintext attacks. Performance and security aspects of encryption scheme is analyzed both quantitatively using predefined security metrics and qualitatively by scrutinizing the internal working of encryption scheme. Computational complexity of encrypting a plain image of size (r o w s × c o l u m n s) is 𝒪 (r o w s × c o l u m n s) and is suitable for encrypting keyframes of video for secure surveillance applications. [ABSTRACT FROM AUTHOR]

This paper introduces an efficient and scalable cloud-based privacy preserving model using a new optimal cryptography scheme for anomaly detection in large-scale sensor data. Our proposed privacy preserving model has maintained a better tradeoff between reliability and scalability of the cloud computing resources by means of detecting anomalies from the encrypted data. Conventional data analysis methods have used complex and large numerical computations for the anomaly detection. Also, a single key used by the symmetric key cryptographic scheme to encrypt and decrypt the data has faced large computational complexity because the multiple users can access the original data simultaneously using this single shared secret key. Hence, a classical public key encryption technique called RSA is adopted to perform encryption and decryption of secure data using different key pairs. Furthermore, the random generation of public keys in RSA is controlled in the proposed cloud-based privacy preserving model through optimizing a public key using a new hybrid local pollination-based grey wolf optimizer (LPGWO) algorithm. For ease of convenience, a single private server handling the organization data within a collaborative public cloud data center when requiring the decryption of secure sensor data are allowed to decrypt the optimal secure data using LPGWO-based RSA optimal cryptographic scheme. The data encrypted using an optimal cryptographic scheme are then encouraged to perform data clustering computations in collaborative public servers of cloud platform using Neutrosophic c-Means Clustering (NCM) algorithm. Hence, this NCM algorithm mainly focuses for data partitioning and classification of anomalies. Experimental validation was conducted using four datasets obtained from Intel laboratory having publicly available sensor data. The experimental outcomes have proved the efficiency of the proposed framework in providing data privacy with high anomaly detection accuracy. [ABSTRACT FROM AUTHOR]

The goal of an outdegree-constrained edge-modification problem is to find a spanning subgraph or supergraph H of an input undirected graph G such that either: (Type I) the number of edges in H is minimized or maximized and H can be oriented to satisfy some specified constraints on the vertices' resulting outdegrees; or: (Type II) among all subgraphs or supergraphs of G that can be constructed by deleting or inserting a fixed number of edges, H admits an orientation optimizing some objective involving the vertices' outdegrees. This paper introduces eight new outdegree-constrained edge-modification problems related to load balancing called (Type I) MIN-DEL-MAX, MIN-INS-MIN, MAX-INS-MAX, and MAX-DEL-MIN and (Type II) p -DEL-MAX, p -INS-MIN, p -INS-MAX, and p -DEL-MIN. In each of the eight problems, the input is a graph and the goal is to delete or insert edges so that the resulting graph has an orientation in which the maximum outdegree (taken over all vertices) is small or the minimum outdegree is large. We first present a framework that provides algorithms for solving all eight problems in polynomial time on unweighted graphs. Next we investigate the inapproximability of the edge-weighted versions of the problems, and design polynomial-time algorithms for six of the problems on edge-weighted trees. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the direction of arrival (DOA) estimation problem of noncircular signals for coprime linear array (CLA). From the perspective of the CLA as extracted from a filled uniform linear array (ULA), a noncircular root-MUSIC algorithm is proposed to estimate the DOA which can avoid the spectral peak search and lower the computational complexity. Due to the noncircular characteristic, the proposed algorithm enables to resolve more sources than sensors. Meanwhile, the proposed algorithm has better angle estimation performance than some conventional DOA estimation algorithms. Numerical simulation results illustrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

Detecting communities is one of the important research directions in social network analysis currently. However, complexity and size of real world networks makes it practically impossible to develop a unique mechanism for finding communities, which will show satisfactory results in almost any network. In this paper, we have proposed a genetic method that can detect communities in social networks extracted from the Web. Advantage of the method is that we can set an upper boundary to the number of clusters in the network. This is achieved by means of information centrality. When we choose top p nodes, which shall be used in the algorithm iteration, we know that the number of clusters in the network is less that the number p. Yet another advantage of the method is that it is fast with computational complexity equals O (n 2 p). This is a huge improvement compared to most algorithms with convergence speed O (n 3). The experimental results verify the superior performance of the proposed method. [ABSTRACT FROM AUTHOR]

For the virtual reality 360 ∘ videos, equirectangular projection (ERP) is a commonly used projection format. However, its high resolution brings extraordinary huge computational complexity in encoding. In order to speed up the intra coding process, a fast coding unit (CU) partitioning algorithm based on regional decision tree is proposed in this paper. The frame image is divided into two regions from a statistical point of view, and the earlysplit and pruned decision trees are established using light weight sample attributes for each region. With the help of these decision trees, the CU partitioning process is accelerated. Compared with the original algorithm of HM16.20, the proposed algorithm can reduce the encoding time by 28%, while BD-rate only increases by 0.27%. [ABSTRACT FROM AUTHOR]

There are many examples of failed strategies whose intention is to optimize a process but instead they produce worse results than no strategy at all. Many fall under the loose umbrella of the "no free lunch theorem". In this paper we present an example in which a simple (but assumedly naive) strategy intended to shorten proof lengths in the propositional calculus produces results that are significantly worse than those achieved without any method to try to shorten proofs.This contrast with what was to be expected intuitively, namely no improvement in the length of the proofs. Another surprising result is how early the naive strategy failed. We set up a experiment in which we sample random classical propositional theorems and then feed them to two very popular automatic theorem provers (AProS and Prover9). We then compared the length of the proofs obtained under two methods: (1) the application of the theorem provers with no additional information; (2) the addition of new (redundant) axioms to the provers. The second method produced even longer proofs than the first one. [ABSTRACT FROM AUTHOR]

In this paper, a new auto-scoring algorithm that automatically evaluates the Berg balance scale (BBS) tasks is proposed. The BBS can be used as an indicator for patients to analyze their rehabilitation status by themselves. In the proposed method, the patient must use a wearable inertial measurement unit (IMU) sensor, and the result of the patient's BBS task execution would be scored automatically by the evaluation algorithm. The proposed evaluation algorithm involves only few computations and has high scoring accuracy. Nonlinear kernel principal component analysis and a small number of linear features were combined to reduce the features from each sensor, and the algorithm model was implemented using a support vector machine (SVM), a machine learning technique with low computational complexity. The effectiveness of the algorithm was evaluated through clinical evaluation of 53 subjects with up to eight IMU sensors. The average accuracy of the proposed algorithm using eight sensors was 93.2%, and that using five sensors was 91.5%. There was a 12.6% and 10.9% increase in accuracy, respectively, compared to a previous study. The training and testing times of the proposed SVM model were over 38 times faster than the multi-layer perceptron model used in a previous study. [ABSTRACT FROM AUTHOR]

The security of chaotic cryptographic system can be theoretically evaluated by using conventional statistical tests and numerical simulations, such as the character frequency test, entropy test, avalanche test and SP 800-22 tests. However, when the cryptographic algorithm operates on a cryptosystem, the leakage information such as power dissipation, electromagnetic emission and time-consuming can be used by attackers to analyze the secret keys, namely the Side Channel Analysis (SCA) attack. In this paper, a cryptanalysis method is proposed for evaluating the security of a chaotic block cryptographic system from a hardware perspective by utilizing the Template Attacks (TAs). Firstly, a chaotic block cryptographic system is described briefly and implemented based on an Atmel XMEGA microcontroller. Then the TA using a multivariate Gaussian model is introduced. In order to reduce computational complexity and improve the efficiency of TA, the Hamming weight is used in this work to model power consumption traces. The proposed TA method has the following advantages including (a) using the sum of difference to select points of interest of traces, (b) using a data processing method to minimize the influences on power information modeling from the redundant sampling points, and (c) all the traces are aligned precisely before establishing the templates. Experimental results show that the TA can be used to attack the chaotic cryptographic systems and is more efficient, i.e. ∼ 32% less attack traces than correlation power analysis, when the templates are properly built. [ABSTRACT FROM AUTHOR]

The running time of a quantum walk search algorithm depends on both the structure of the search space (graph) and the configuration (the placement and the number) of marked locations. While the first dependence has been studied in a number of papers, the second dependence remains mostly unstudied. We study search by quantum walks on the two-dimensional grid using the algorithm of Ambainis, Kempe and Rivosh [3]. The original paper analyses one and two marked locations only. We move beyond two marked locations and study the behaviour of the algorithm for several configurations of multiple marked locations. In this paper, we prove two results showing the importance of how the marked locations are arranged. First, we present two placements of k marked locations for which the number of steps of the algorithm differs by a factor of Ω(k). Second, we present two configurations of k and k marked locations having the same number of steps and probability of finding a marked location. [ABSTRACT FROM AUTHOR]

The relationship between frames and Parseval frames is an important topic in frame theory. In this paper, we investigate Parseval transforms, which are linear transforms turning general finite frames into Parseval frames. We introduce two classes of transforms in terms of the right regular and left Parseval transform matrices (RRPTMs and LPTMs). We give representations of all the RRPTMs and LPTMs of any finite frame. Two important LPTMs are discussed in this paper, the canonical LPTM (square root of the inverse frame operator) and the RGS matrix, which are obtained by using row's Gram-Schmidt orthogonalization. We also investigate the relationship between the Parseval frames generated by these two LPTMs. Meanwhile, for RRPTMs, we verify the existence of invertible RRPTMs for any given finite frame. Finally, we discuss the existence of block diagonal RRPTMs by taking the graph structure of the frame elements into consideration. [ABSTRACT FROM AUTHOR]

In the paper [H. Abulkasim et al., Int. J. Quantum Inform. 15 (2017) 1750023], Abulkasim et al. proposed a quantum secret sharing scheme based on Bell states. We study the security of the multiparty case in the proposed scheme and detect that it is not secure. In the paper [Y. Du and W. Bao, Opt. Commun. 308 (2013) 159], Du and Bao listed Gao's scheme and gave a attack strategy on the listed scheme. We point out that their listing scheme is not the genuine Gao's scheme and their research method is not advisable. [ABSTRACT FROM AUTHOR]

The Resource Allocation Problem with Time Dependent Penalties (RAPTP) is a variant of uncapacitated resource allocation problems generally referred as uncapacitated facility allocation problems or uncapacitated facility location problem (UFLP). Work done in this paper is motivated by the work of Du, Lu and Xu [7] in which authors considered facility location problems with submodular penalties and presented a 3-approximation primal dual algorithm. This paper considers that each unallocated demand point adds to penalty that increases as time passes and is thus represented by function x (t i , p i) where t i and p i are elapse time and priority of demand point d i . As this problem has been considered for emergency service allocation, all demand points should be allocated to some facility or resource within some stipulated time limit beyond which it may lose its purpose. Thus penalty incurred by a demand point is considered till that threshold value only. Thus it is assumed that penalty contribution by a demand point remains constant after a specified threshold value. By exploiting the properties of time dependent penalties, a 4-approximation primal-dual algorithm is proposed which is based on LP framework, and is the first constant-factor approximation algorithm for RAPTP. [ABSTRACT FROM AUTHOR]

The exact controllability can be mapped to the problem of maximum algebraic multiplicity of all eigenvalues. In this paper, we focus on the exact controllability of deterministic complex networks. First, we explore the eigenvalues of two famous networks, i.e. the comb-of-comb network and the Farey graph. Due to their special structure, we find that the eigenvalues of each network are mutually distinct, showing that these two networks are optimal networks with respect to exact controllability. Second, we study how to optimize the exact controllability of a deterministic network. Based on the spectral graph theory, we find that reducing the order of duplicate sets or co-duplicate sets which are two special vertex subsets can decrease greatly the exact controllability. This result provides an answer to an open problem of Li et al. [X. F. Li, Z. M. Lu and H. Li, Int. J. Mod. Phys. C 26, 1550028 (2015)]. Finally, we discuss the relation between the topological structure and the multiplicity of two special eigenvalues and the computational complexity of our method. [ABSTRACT FROM AUTHOR]

The morbidity of cardiovascular disease increasingly rises, which makes great impact upon people's health and life. Electrocardiogram (ECG) beat classification is of great significance to clinical diagnosis of cardiovascular diseases. Traditional ECG signal classification algorithm relies heavily on the accuracy of feature extraction or increases the complexity of the calculation process by means of the correlation characteristic coefficient transformation, which results in that the ECG beat classification effect is still not satisfactory. Aimed at this problem, a novel method based on convolution neural network (CNN) is presented in this paper. First, ECG signal is preprocessed to suppress the noise and to locate the R peaks, and five kinds of ECG beat waveform data are obtained. Then taking ECG beat sampling points as input, four layers of one-dimensional CNN are constructed for feature extraction and classification. Finally, experimental verification is carried out on the data from MIT-BIH database, and the accuracy of recognition and classification of the presented method reaches 99.10%. Comparison with the methods based on artificial features, this method shows better performance, which avoids serious dependence on the accuracy of feature extraction, skips the steps of feature extraction and selection, and reduces the complexity of computational process. [ABSTRACT FROM AUTHOR]

Recently, Kieu derived a new class of time–energy uncertainty relations, which is not only formal but also suitable for evaluating the speed limit of quantum dynamics. However, when this time–energy uncertainty relation was applied to study the quantum adiabatic Grover's search, some approximation had been done for reaching the right conclusion. That is, the final state being orthogonal to the initial state in this problem was assumed which may cause confusion, while the truth is that the overlap between these two states is indeed very small when the problem size is very big but not equal to zero exactly. In this paper, we modify the time–energy uncertainty relation of Kieu applied to two quantum evolutions of Grover's problem, and find that the resulting computational complexities match well with the previous works on this topic but without the need of making the assumption like that in the work of Kieu. [ABSTRACT FROM AUTHOR]