Search

Correlation clustering problem (CorCP) is a classical clustering problem, which clusters data based on the similarity of data set, and has many applications in interaction networks, cross-lingual link detection, and communication networks, etc. In this paper, we study a practical generalization of the CorCP, called the capacitated correlation clustering problem (the capacitated CorCP), by constructing a labeled complete graph. On this labeled complete graph, each vertex represents a piece of data. If two pieces of data are similar, then the edge between the corresponding vertices is marked by a positive label +. Otherwise, this edge is marked by a negative label -. The objective of the capacitated CorCP is to group some similar data sets into one cluster as far as possible, while satisfying the cluster capacity constraint. To achieve this objective, we shall partition the vertex set of the labeled complete graph into several clusters, each cluster's size subjecting to an upper bound, so as to minimize the number of disagreements. Here the number of disagreements is defined as the total number of the edges with positive labels between clusters and the edges with negative labels within clusters. Different with the previous algorithm in [18], which subjects to the constraint on the cluster size by a penalty measure, we design an algorithm for the capacitated CorCP to directly output a feasible solution by iteratively constructing clusters based on a preset threshold. Through carefully setting the threshold and sophisticatedly analyzing, our algorithm is proved to have an improved approximation ratio of 5.37. In addition, we also conduct a series of numerical experiments to demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

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

Let = { T 1 , T 2 , ... , T k } be a set of k ≥ 2 spanning trees in a graph G. The k spanning trees are called completely independent spanning trees (CISTs for short) if the paths joining every pair of vertices x and y in any two trees have neither vertex nor edge in common except for x and y. Particularly, is called a dual-CIST provided k = 2. For data transmission applications in reliable networks, the existence of a dual-CIST can provide a configuration of fault-tolerant routing called protection routing. This paper investigates the problem of constructing a dual-CIST in the n -dimensional hierarchical folded cubic network H F Q n . The network is a two-level network using folded hypercube F Q n as clusters to reduce the diameter, hardware overhead and improve the fault tolerance ability. We propose a recursive algorithm to construct a dual-CIST of H F Q n in (2 2 n) time for n ≥ 2 , where the time required is the same scale as the number of vertices of H F Q n . Also, the diameter of each constructed CIST is 4 n + 1. [ABSTRACT FROM AUTHOR]

Robust subgroup multisignature allows any subgroup of signers from a global set to sign a given message on behalf of the whole group, and the individual signatures should be verified before the combination process, which resists poison signature attacks. An emerging application of robust subgroup multisignatures in blockchain is that a qualified subgroup of a global set of users has reached agreement. In the integrated blockchain and edge computing system, the edge server can naturally act as a combiner in multisignatures and help other end devices produce the final aggregate signature. In this paper, we propose a robust subgroup multisignature with one-time public keys in order that has two advantages for solving the signers ordering problem and one-time public key problem simultaneously. Our scheme is a nontrivial extension of Galindo et al.'s robust subgroup multisignature scheme and can be proven unforgeable, robust and chronological in random oracles. Our scheme can also be suitable for the consortium blockchain by adding a noninteractive zero-knowledge (NIZK) proof system for certifying the one-time public keys. [ABSTRACT FROM AUTHOR]

The Maximum Independent Set problem is well-studied in graph theory and related areas. An independent set of a graph is a subset of non-adjacent vertices of the graph. A maximum independent set is an independent set of maximum size. This paper studies the Maximum Independent Set problem in some classes of geometric intersection graphs in a distributed setting. More precisely, we study the Maximum Independent Set problem on two geometric intersection graphs, interval and axis-parallel segment intersection graphs, and present deterministic distributed algorithms in a model that is similar but a little weaker than the local communication model. We compute the maximum independent set on interval graphs in O(k) rounds and O(n) messages, where k is the size of the maximum independent set and n is the number of nodes in the graph. We provide a matching lower bound of Ω(k) on the number of rounds, whereas Ω(n) is a trivial lower bound on message complexity. Thus, our algorithm is both time and message-optimal. We also study the Maximum Independent Set problem in interval count l graphs, a special case of the interval graphs where the intervals have exactly l different lengths. We propose an 1 2-approximation algorithm that runs in O(l) round. For axis-parallel segment intersection graphs, we design an 1 2-approximation algorithm that obtains a solution in O(D) rounds. The results in this paper extend the results of Molla et al. [J. Parallel Distrib. Comput. 2019]. [ABSTRACT FROM AUTHOR]

The concept of vulnerability in a communication network plays an important role when there is a disruption in the network. There exist several graph parameters that measure the vulnerability of a communication network. Domination integrity is one of the vulnerability parameters that measure the performance of a communication network. In this paper, we introduce the concept of paired domination integrity of a graph as a new measure of graph vulnerability. Let G = (V,E) be a simple, connected graph. A set of vertices in a graph G, say S, is a paired dominating set if the following two conditions are satisfied: (i) every vertex of G has a neighbor in S and (ii) the subgraph induced by S contains a perfect matching. The paired domination integrity of G, denoted by PDI(G), is defined as PDI(G) = min{|S| + m(G − S) : S is a paired dominating set of G}, where m(G − S) is the order of the largest component in the induced subgraph of G − S. In this paper, we determine few bounds relating paired domination integrity with other graph parameters and the paired domination integrity of some classes of graphs. [ABSTRACT FROM AUTHOR]

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]

Rotation symmetric Boolean functions are good candidates for stream ciphers because they have such advantages as simple structure, high operational speed and low implement cost. Recently, Mesnager et al. proposed for the first time an efficient method to construct balanced rotation symmetric Boolean functions with optimal algebraic immunity and good nonlinearity for an arbitrary even number of variables. However, the algebraic degree of their constructed n -variable (n > 4) function is always less than the maximum value n − 1. In this paper, by modifying the support of Boolean functions from Mesnager et al.'s construction, we present two new constructions of balanced even-variable rotation symmetric Boolean functions with optimal algebraic immunity as well as higher algebraic degree and nonlinearity. The algebraic degree of Boolean functions in the first construction reaches the maximum value n − 1 if n 2 is odd and n 2 ≠ (2 k + 1) 2 or (2 k + 1) 2 + 2 for integer k , while that of the second construction reaches the maximum value for all n. Moreover, the nonlinearities of Boolean functions in both two constructions are higher than that of Mesnager et al.'s construction. [ABSTRACT FROM AUTHOR]

This paper introduces a framework for building probabilistic models with subsequential failure transducers. We first show how various types of subsequential transducers commonly used in natural language processing are represented by conditional probabilistic subsequential transducers and probabilistic subsequential failure transducers. Afterwards, we introduce efficient algorithms for composition of conditional probabilistic subsequential transducers with probabilistic subsequential failure transducers and canonization (weight-pushing) of probabilistic subsequential failure transducers. Those algorithms are applicable to many tasks for representing probabilistic models. One such task is the construction of the H C L G weighted transducer used in speech recognition which we describe in detail. At the end, a comparison between the presented H C L G failure weighted transducer and the standard H C L G weighted transducer along with empirical results for HMM-based speech recognition decoding reveal the competitiveness of the presented constructions. [ABSTRACT FROM AUTHOR]

The rapid expansion of infrastructure topology, especially noticeable in high-performance computing systems and data center networks, significantly increases the likelihood of failures in network components. While traditional (edge) connectivity has long been the standard for measuring the reliability of interconnection networks, this approach becomes less effective as networks grow more complex. To address this, two innovative metrics, named matroidal connectivity and conditional matroidal connectivity, have emerged. These metrics provide the flexibility to impose constraints on faulty edges across different dimensions and have shown promise in enhancing the edge fault tolerance of interconnection networks. In this paper, we explore (conditional) matroidal connectivity of the k-dimensional folded Petersen network FPk, which is constructed by iteratively applying the Cartesian product operation on the well-known Petersen graph and possesses a regular, vertex- and edge-symmetric architecture with optimal connectivity and logarithmic diameter. Specifically, the faulty edge set F is partitioned into k subsets according to the dimensions of FPk. We then arrange these subsets by their cardinality, imposing the restriction whereby the cardinality of the ith largest subset dose not exceed 3 ⋅ 10i−1 for 1 ≤ i ≤ k. Subsequently, we show that FPk − F is connected with |F|≤∑i=1k(3 ⋅ 10i−1) and determine the exact value of matroidal connectivity and conditional matroidal connectivity. [ABSTRACT FROM AUTHOR]

With the rapid expansion of multiprocessor systems, the fault diagnosis is becoming more and more important. The h-component diagnosability of a multiprocessor system, is proposed to extend the traditional diagnosability and has been investigated widely. In this paper, we prove that under both the PMC model and MM* model the 2-component and 3-component diagnosability of an n-dimensional alternating group graph are 2n − 5 and 3n − 7 respectively. [ABSTRACT FROM AUTHOR]

Many real-world applications arising from social networks, personalized recommendations, and others, require extracting a relatively small but broadly representative portion of massive data sets. Such problems can often be formulated as maximizing a monotone set function with cardinality constraints. In this paper, we consider a streaming model where elements arrive quickly over time, and create an effective, and low-memory algorithm. First, we provide the first single-pass linear-time algorithm, which is a a deterministic algorithm, achieves an approximation ratio of [ γ 4 a (1 + γ + γ 2 + γ 3) − ] for any ≥ 0 with a query complexity of ⌈ n / a ⌉ + a and a memory complexity of O (a k log (k) log (1 /)) , where a is a positive integer and γ is the submodularity ratio. However, the algorithm may produce less-than-ideal results. Our next result is to describe a multi-streaming algorithm, which is the first deterministic algorithm to attain an approximation ratio of 1 − e − γ − with linear query complexity. [ABSTRACT FROM AUTHOR]

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

The main complexity classes of the Parameterized Intractability Theory are based on weighted Boolean circuit satisfiability problems and organized into a hierarchy so-called W-hierarchy. The W-hierarchy enables fine-grained complexity analyses of parameterized problems that are unlikely to belong to the FPT class. In this paper, we introduce the Th-hierarchy, a natural generalization of the W-hierarchy defined by unweighted threshold circuit satisfiability problems. Investigating the relationship between Th-hierarchy and W-hierarchy, we discuss the complexity of transforming Threshold circuits into Boolean circuits, and observe that sorting networks are powerful tools to handle such transformations. First, we show that these hierarchies collapse at the last level (W[P] = Th[P]). After that, we present a time complexity analysis of an AKS sorting network construction, which supports some of our results. Finally, we prove that Th[ t ] ⊆ W[SAT] for every t ∈ ℕ. As a by-product, our studies suggest that it is relevant to consider a new class based on logarithmic depth circuits in the W-hierarchy. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

Let n , k and t be non-negative integers. The generalized Johnson graph G (n , k , t) is the graph whose vertices are the k -subsets of the set { 1 , 2 , ... , n } , and two vertices are adjacent if and only if they intersect with t elements. Special cases of generalized Johnson graph include the Kneser graph G (n , k , 0) and the Johnson graph G (n , k , k − 1). These graphs play an important role in coding theory, Ramsey theory, combinatorial geometry and hypergraphs theory. In this paper, we discuss the connectivity properties of the Kneser graph G (n , k , 0) and G (n , k , 1) by their symmetric properties. Specifically, with the help of some properties of vertex/edge-transitive graphs we prove that G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) are super restricted edge-connected. Besides, we obtain the exact value of the restricted edge-connectivity and the cyclic edge-connectivity of the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) and G (n , k , 1) (4 ≤ 2 k ≤ n) , and further show that the Kneser graph G (n , k , 0) (5 ≤ 2 k + 1 ≤ n) is super vertex-connected and super cyclically edge-connected. [ABSTRACT FROM AUTHOR]

This paper analyzes two schemes from a 2019 work by Liu, Yang, Han and Wang, namely, adapting the McEliece cryptosystem to obtain a new public-key encryption scheme, and designing an efficient CFS-like digital signature. It is shown that the new encryption scheme based on McEliece, even if it has longer public keys, is not more secure than the standard one. The security gap between the original scheme and its modification is presented. Moreover, while the proposed parameters for the digital signature scheme lead to a significant performance improvement, however, they introduce a vulnerability in the protocol. A key-forgery attack using the Support Splitting Algorithm as a subroutine is described, with a study of the computational cost of retrieving the secret key from the public one. [ABSTRACT FROM AUTHOR]

Given an n -vertex graph G with a fixed linear ordering of V (G) and two integers k , b , the problem FIXED-ORDER BOOK DRAWING with few crossings per edge asks whether or not G admits a k -page book drawing where the maximum number of crossings per edge can be upper bounded by the number b. This problem was posed as an open question by Bhore et al. (J. Graph Algorithms Appl. 2020). In this paper, we study this problem from the viewpoint of parameterized complexity, in particular, we develop fixed-parameter tractable algorithms for it. More specifically, we show that this problem parameterized by both the bound number b of crossings per edge and the vertex cover number τ of the input graph admits an algorithm with running time in (b + 2) (τ 3) ⋅ n , and this problem parameterized by both the bound number b of crossings per edge and the pathwidth κ of the vertex ordering admits an algorithm with running time in (b + 2) (κ 2) ⋅ n. Our results provide a specific answer to Bhore et al.'s question. [ABSTRACT FROM AUTHOR]

Since 2000, the real estate industry has experienced rapid development, and at the same time, it has driven the rapid growth of housing prices, and the trend of housing prices has attracted attention. This paper integrates genetic algorithm and particle swarm algorithm to optimize BP neural network, and establishes a housing price prediction model based on mixed genetic particle swarm BP neural network. The average data of housing prices in Chongqing, China from 2000 to 2020 and several main factors affecting the trend of housing prices were selected as experimental data. Through the training and simulation prediction based on the mixed particle swarm BP neural network, the error between the predicted value and the actual value was within 0.5%, the validity and accuracy of the model are proved. At the same time, this paper predicts the average price of residential commercial housing in Chongqing in 2021, which provides a reference for the government's macro-control and sellers to carry out residential commercial housing. [ABSTRACT FROM AUTHOR]

This paper uses multi-sensor data fusion technology to design and develop a multi-sensor based basketball robot's target recognition and positioning system in an unknown environment. We establish the movement model of the basketball robot, and combine the hardware configuration of the basketball robot, analyse the methods of speed control, position control, and direction control, propose a fuzzy obstacle avoidance strategy in the basketball robot movement process, and simulate the obstacle avoidance strategy. The simulation results show that the proposed fuzzy obstacle avoidance strategy is effective. Carry out the experiment of basketball robot target calibration, build the basketball robot monitoring system, and realize data transmission and real-time image processing. Experiments show that the basketball robot can achieve target recognition and positioning tasks in an unknown environment (obstacle comparison rules). It proves the effectiveness and robustness of the proposed following algorithm. It illustrates the effectiveness of the system designed in this paper. [ABSTRACT FROM AUTHOR]

This paper is based on fuzzy clustering algorithm on financial data, design of financial data mining system and analysis of financial data, analysis of financial data on the financial decision-making mechanism, from financial data how to enhance the information base of the forecast, financial data how to improve the pertinence of decision-making, financial data how to build a new competitive advantage, financial data how to promote the dynamic decision-making of four, through the analysis of data in financial decision-making specific implementation cases, focusing on the real-life problems faced by the management and the effect of financial data platform to solve problems; finally, through this paper, we hope to provide reference and reference for other similar enterprises to apply financial data for financial decision-making. This paper first describes the theory of financial data, analyzes the mechanism of financial data and financial decision-making, how financial data enhance the information base of forecasting, how financial data improve the pertinence of decision-making, how financial data build a new competitive advantage, how financial data promote dynamic decision-making four dimensions to summarize. [ABSTRACT FROM AUTHOR]

In this paper, we propose a logic-based characterization of uncertainty in architectures of parametric component-based systems, where the parameter is the number of instances of each component type. For this, we firstly introduce an extended propositional interaction logic over De Morgan algebras and we show that its formulas can encode the uncertainty of several architectures applied in systems with a finite number of components. In turn, we introduce a first-order extended interaction logic over De Morgan algebras which is applied for modelling uncertainty in the interactions of well-known parametric architectures. Moreover, we prove that the equivalence problem for a large class of formulas of that logic is decidable in doubly exponential time by providing an effective translation to fuzzy recognizable series. For any such formula over a totally ordered De Morgan algebra, we further prove that we can compute in exponential time the set of sequences of parametric fuzzy interactions which ensure the trustworthiness of the formula according to a particular threshold. [ABSTRACT FROM AUTHOR]

This paper considers a transportation problem on a weighted graph. The weights specify the amounts of commodities at nodes, which are positive if the amounts are stored at nodes and negative if the amounts are needed at nodes. To meet all demands we use vehicles, one at each node, with some loading capacity to and from neighbors. In a trip using a vehicle we can send commodities from a node to a neighbor along an edge and also bring back some other commodities from the neighbor. In this paper we are interested in feasibility problem, which is to decide whether there is a single round of trips that meet all demands. We prove the feasibility problem is NP-complete even in the easiest case of a one-commodity transportation problem with unbounded capacity. We also present several different polynomial-time algorithms for other cases. [ABSTRACT FROM AUTHOR]

Although regular expressions do not correspond univocally to regular languages, it is still worthwhile to study their properties and algorithms. For the average case analysis one often relies on the uniform random generation using a specific grammar for regular expressions, that can represent regular languages with more or less redundancy. Generators that are uniform on the set of expressions are not necessarily uniform on the set of regular languages. Nevertheless, it is not straightforward that asymptotic estimates obtained by considering the whole set of regular expressions are different from those obtained using a more refined set that avoids some large class of equivalent expressions. In this paper we study a set of expressions that avoid a given absorbing pattern. It is shown that, although this set is significantly smaller than the standard one, the asymptotic average estimates for the size of the Glushkov automaton for these expressions does not differ from the standard case. Furthermore, for this set the asymptotic density of 휀-accepting expressions is also the same as for the set of all standard regular expressions. [ABSTRACT FROM AUTHOR]

The k-set tree connectivity, as a natural extension of classical connectivity, is a very important index to evaluate the fault-tolerance of interconnection networks. Let G = (V,E) be a connected graph and a subset S ⊆ V, an S-tree of graph G is a tree T = (V′,E′) that contains all the vertices of S and E(T) ⊆ E(G). Two S-trees T and T′ are internally disjoint if and only if E(T) ∩ E(T′) = ∅ and V (T) ∩ V (T′) = S. The cardinality of maximum internally disjoint S-trees is defined as κG(S), and the k-set tree connectivity is defined by κk(G) =min{κG(S)|S ⊆ V (G) and |S| = k}. In this paper, we show that the k-set tree connectivity of folded hypercube when k = 4, that is, κ4(FQn) = n, where FQn is folded hypercube for n ≥ 2. [ABSTRACT FROM AUTHOR]

The longest increasing subsequence (LIS) problem aims to find the subsequence exhibiting an increasing trend in a numeric sequence with the maximum length. In this paper, we generalize the LIS problem to the longest wave subsequence (LWS) problem, which encompasses two versions: LWSt and LWSr. Given a numeric sequence A of distinct values and a target trend sequence T, the LWSt problem aims to identify the longest subsequence of A that preserves the trend of the prefix of T. And, the LWSr problem aims to find the longest subsequence of A within r segments, alternating increasing and decreasing subsequences. We propose two efficient algorithms for solving the two versions of the LWS problem. For the LWSt problem, the time complexity of our algorithm is O(nlog n), where n represents the length of the given numeric sequence A. Additionally, we propose an O(rnlog n)-time algorithm for solving the LWSr problem. In both algorithms, we utilize the priority queues for the insertion, deletion, and successor operations. [ABSTRACT FROM AUTHOR]

Finite automata that traverse graphs by moving along their edges are known as graph-walking automata (GWA). This paper investigates the state complexity of Boolean operations for this model. It is proved that the union of GWA with m and n states, with m ≤ n, operating on graphs with k labels of edge end-points, is representable by a GWA with 2km + n + 1 states, and at least 2(k − 3)(m − 1) + n − 1 states are necessary in the worst case. For the intersection, the upper bound is (2k + 1)m + n and the lower bound is 2(k − 3)(m − 1) + n − 1. The upper bound for the complementation is 2kn + 1, and the lower bound is 2(k − 3)(n − 1). [ABSTRACT FROM AUTHOR]

A graph G = (V (G),E(G)) is called a k-dot product graph if there is a function f : V (G)→ℝk such that for any two distinct vertices u and v, f(u).f(v) ≥ 1 if and only if uv ∈ E(G). The minimum value k such that G is a k-dot product graph, is called the dot product dimension ρ(G) of G. In this paper, we give an efficient algorithm for computing the dot product dimension of outerplanar graphs of at most two edge-disjoint cycles. If the graph has two cycles, we only consider those outerplanar graphs if both cycles have exactly one vertex in common and the length of one of the cycles is greater than or equal to six. [ABSTRACT FROM AUTHOR]

The error-correcting pair is a general algebraic decoding method for linear codes. Since every linear code is contained in an MDS linear code with the same minimum distance over some finite field extensions, we focus on MDS linear codes. Recently, He and Liao showed that for an MDS linear code 풞 with minimum distance 2ℓ + 2, if it has an ℓ-error-correcting pair, then the parameters of the pair have three possibilities. Moreover, for the first case, they gave a necessary condition for an MDS linear code 풞 with minimum distance 2ℓ + 2 to have an ℓ-error-correcting pair, and for the other two cases, they only gave some counterexamples. For the second case, in this paper, we give a necessary condition for an MDS linear code 풞 with minimum distance 2ℓ + 2 to have an ℓ-error-correcting pair, and then basing on the Product Singleton Bound, we prove that there are two cases for such pairs, and then give some counterexamples basing on twisted generalized Reed–Solomon codes for these cases. [ABSTRACT FROM AUTHOR]

The notion of c-differential uniformity was proposed by Ellingsen et al., which generalizes the classical differential uniformity measuring the resistance against differential cryptanalysis. Since then, the research of functions with low c-differential uniformity over finite fields attracted many researchers’ attention. However, it seems that there is no study of function with low c-differential uniformity over integer rings modulo n. In this paper, we give an extension of the c-differential uniformity concept to rings of integers module some n > 0, and we present several perfect c-nonlinear polynomial functions on the integer ring ℤn for the different integer n. [ABSTRACT FROM AUTHOR]

In this paper, we present a generic construction of r-ary sequences with period pq2 based on the Euler quotient modulo pq, where p and q are odd primes satisfying that p divides q − 1 and r is any prime less than q. The minimal polynomial and the linear complexity of the proposed sequences are determined in most cases under the assumption that rq−1≢1 (mod q2). The result shows that each of the sequences has large linear complexity. [ABSTRACT FROM AUTHOR]

Let G be the complete Euclidean graph on a set of points embedded in the plane. Given a constant t > 1 , a spanning subgraph G ′ of G is said to be a t -spanner, or simply a spanner, if for any pair of nodes p , q in G there exists a t -path in G ′ , i.e., a path between p and q whose length is at most t times their distance in G. Gap-greedy spanner, proposed by Arya and Smid, is a light weight and bounded degree spanner in which a pair of points p , q is guaranteed to have a t -path, if there exists at least one edge with some special criteria in the spanner. Existing algorithms for computing the gap-greedy spanner determine the existence of such an edge for each pair of points by examining the edges of the spanner, which takes O (n) time, however in this paper, we have presented a method by which this task can be done in O (1) time. Using the proposed method and well-separated pair decomposition, we have proposed a linear-space algorithm that can compute the gap-greedy spanner in O (n 2) time. How to use the well-separated pair decomposition to compute this spanner was proposed by Bakhshesh and Farshi, however using an example, we have shown that one of the algorithms they have proposed for this purpose is incorrect. We have performed various experiments to measure the duration and amount of memory used by the algorithms for computing this spanner. The results of these experiments showed that the proposed method, without a significant effect on the amount of memory consumed compared to previous algorithms, leads to a significant acceleration in the construction time of this spanner. [ABSTRACT FROM AUTHOR]

The fault diameter and wide diameter are commonly used to measure the fault tolerance and transmission delay of interconnection networks beyond traditional diameter. The α -wide diameter of graph G , denoted by D α (G) , is the minimum integer l such that there exist at least α internally vertex disjoint paths of length at most l for any two distinct vertices in G. The β -fault diameter of graph G , denoted by D β f (G) , is the maximum diameter of the survival graph obtained by deleting at most β vertices in G. The exchanged crossed cube, as a compounded interconnection network denoted by E C Q (s , t) , holds the desirable properties of both crossed cube and exchanged hypercube, while achieving a better balanced between cost and performance of the parallel computing systems. In this paper, we construct s + 1 internally vertex disjoint paths between any two distinct vertices of E C Q (s , t). Moreover, we determine the upper and lower bounds of (s + 1) -wide diameter and s -fault diameter of E C Q (s , t) , i.e., ⌈ s 2 ⌉ + ⌈ t + 1 2 ⌉ + 4 ≤ D s f (E C Q (s , t)) ≤ D s + 1 (E C Q (s , t)) ≤ ⌈ s + 1 2 ⌉ + ⌈ t + 1 2 ⌉ + 5 , which shows that the exchanged crossed cube has better efficiency and reliability than that of the exchanged hypercube. [ABSTRACT FROM AUTHOR]

Networks are known to be prone to node or link failures. A central issue in the analysis of networks is the assessment of their stability and reliability. A central concept that is used to assess stability and robustness of the performance of a network under failures is that of vulnerability. Node and link residual closeness are novel sensitive graph based characteristics for network vulnerability analysis. Node and link residual closeness measure the vulnerability even when the removal of nodes or links does not disconnect the network. Node and link residual closeness are of great theoretical and practical significance to network design and optimization. In this paper, vulnerabilities of multipartite network type topologies to the failure of individual nodes and links are computed via node and link residual closeness which provides a much fuller characterization of the network. Then, how multipartite network type topologies perform when they suffer a node or a link failure is analyzed. [ABSTRACT FROM AUTHOR]

Reaction systems are well-known formal models of interactions between biochemical reactions. A reaction system is a finite set of triples (reactants, inhibitors, products) that represent chemical reactions, where the reactants, the inhibitors, and the products are objects corresponding to the chemicals. The reactions may facilitate or inhibit each other. A distributed reaction system consists of a finite set of reaction systems that interact with their environment (function in a given context). The environment is a finite set of reactants provided by a context automaton. In the preceding paper, we studied distributed reaction systems where in each step, the context automaton provided a separate set of reactants to the component reaction systems. We assigned languages to these distributed reaction systems and provided representations of some well-known language classes by these constructs. In this paper, the context is provided for the whole distributed reaction system and the component reaction systems distribute the context among each other in different ways (the same context is valid for each component, or the context is split among the components). As in the preceding paper, we assign languages to these new types of distributed reaction systems and provide representations of well-known language classes (the class of right-linear simple matrix languages, the recursively enumerable language class). [ABSTRACT FROM AUTHOR]

Multiply constant-weight codes (MCWCs) were introduced recently to improve the reliability of certain physically unclonable function response. In this paper, two methods of constructing MCWCs are presented following the concatenation methodology. In other words, MCWCs are constructed by concatenating approximate outer codes and inner codes. Besides, several classes of optimal MCWCs are derived from these methods. In the first method, the outer codes are q -ary codes and the inner codes are constant-weight codes over G F (2). Furthermore, if the outer code achieves the Plotkin bound and the inner code achieves Johnson bound, then the resulting MCWC is optimal. In the second method, the outer codes are q -ary codes and the inner codes are MCWCs. Furthermore, if the outer code achieves the Plotkin bound and the inner code achieves the Johnson bound, then the resulting MCWC is optimal. [ABSTRACT FROM AUTHOR]

In this paper we combine two classical generalisations of finite automata (weighted automata and automata on infinite words) into a model of integer weighted automata on infinite words and study the universality and the emptiness problems under zero weight acceptance. We show that the universality problem is undecidable for three-state automata by a direct reduction from the infinite Post correspondence problem. We also consider other more general acceptance conditions as well as their complements with respect to the universality and the emptiness problems. Additionally, we build a universal integer weighted automaton with fixed transitions. This automaton has an additional integer input that allows it to simulate any semi-Thue system. [ABSTRACT FROM AUTHOR]

For δ  ∈  ℝ + , maximal δ -repetitions (δ -subrepetitions) are fractional powers in strings with exponent of at least 2 + δ (and 1 + δ , respectively) which are non-extendable with respect to their minimum period. In this paper, we show that in a string S with string attractor Γ there are at most (| Γ | + 2) (⌊ 3 + 6 δ ⌋ ⋅ ⌊ log 1 + δ 4 (| S |) ⌋ + 2) distinct (unpositioned) extended maximal δ -repetitions. Also for any natural number q ≥ 2 the string contains at most (| Γ | + 2) (⌊ 3 + 4 δ ⌋ ⋅ ⌊ log 1 + δ 2 q (| S |) ⌋ + 2) distinct extended maximal δ -subrepetitions without q th powers. We further prove that for fixed δ and q ≥ ⌈ δ + 4 ⌉ , both upper bounds are tight up to a constant factor. [ABSTRACT FROM AUTHOR]

The existence of multiple edge-disjoint Hamiltonian cycles (EDHCs for short) is a desirable property of interconnection networks. These parallel cycles can provide an advantage for algorithms that require a ring structure. Additionally, EDHCs can enhance all-to-all data broadcasting and edge fault tolerance in network communications. In this paper, we investigate the construction of EDHCs in the balanced hypercube, which is a variant of the hypercube with many attractive properties, such as strong connectivity, regularity, and symmetry. In particular, each processor in the balanced hypercube has a backup processor that shares the common neighbors, enabling fault tolerance and efficient system reconfiguration. In 2019, Lü et al. provided an algorithm to construct two EDHCs in an n-dimensional balanced hypercube BHn for n ≥ 2. We further study this topic and give some construction schemes to construct 2⌊log2n⌋ EDHCs in BHn for n ≥ 2. Since BHn is 2n-regular, our result is optimal for n = 2r (r ≥ 1). In addition, we simulate the fault-tolerant data broadcasting through these parallel cycles as transmission channels. [ABSTRACT FROM AUTHOR]

One of the well-known NP-hard optimization problems in graph theory is finding the longest path in a graph. This problem remains NP-hard for general grid graphs, and its complexity is open for grid graphs that have a limited number of holes. In this paper, we study this problem for odd-sized O -shaped grid graphs, i.e. a rectangular grid graph with a rectangular hole. We show that this problem can be solved in linear time. [ABSTRACT FROM AUTHOR]

In recent years, the growth of data has promoted the development of parallel and distributed systems. Graph embedding is of great importance in improving parallel and distributed system performance. The quality of an embedding can be measured by many important metrics, and wirelength is one of the critical metrics related to communication performance and layout costs of physical systems. The hierarchical cubic network is a well-performing interconnection network and the k -rooted complete binary tree is a data structure with a hierarchical relationship among its various elements in algorithms and programming. In this paper, we solve the problem of the embedding of hierarchical cubic networks into k -rooted complete binary trees with minimum wirelength. We first study the optimal set of the hierarchical cubic network, and propose algorithms to give embedding h e t which is an embedding scheme of hierarchical cubic networks into k -rooted complete binary trees with minimum wirelength. Moreover, we give the exact minimum wirelength of this embedding. Finally, we conduct comparative experiments to evaluate the performance of embedding h e t. [ABSTRACT FROM AUTHOR]

The fault tolerance of an interconnection network of parallel and distributed systems can be evaluated by various topological parameters of its underlying graph G, with strong Menger edge connectivity being a vital parameter in this regard. A connected graph G is called strongly Menger edge connected (SM-λ) if it connects any pair of vertices u and v with min{dG(u),dG(v)} number of edge-disjoint paths. Under the uniform distribution of faults in a large interconnection network, it is improbable that each faulty edge incident to a vertex will occur simultaneously. Thus, m-strongly Menger edge connected of order t was introduced in 2018 by He et al. Here, G is called as m-strongly Menger edge connected of order t, if G − F remains SM-λ, where F is an arbitrary edge set in a graph G with |F|≤ m and the minimum degree of the remaining graph δ(G − F) ≥ t. The largest m keeping the property of G − F being SM-λ is denoted as smλt(G). Among variants of hypercube, the n-dimensional folded-crossed hypercube FCQn attracts attention in recent years. In this paper, we focus on calculating the exact value of the maximum conditional edge-fault-tolerant number of order t of FCQn, smλt(FCQ n) = 2t(n + 1 − t) − (n + 1) for two integers 1 ≤ t ≤ n − 2 and n ≥ 3. [ABSTRACT FROM AUTHOR]

This paper studies the problem of dividing m indivisible items among n agents fairly and efficiently. Specifically, this research concentrates on pairwise maximin share (PMMS), which is defined to be the maximum value that an agent can guarantee for herself if she were to repartition the items with another agent and receive the bundle with the minimum value. PMMS is an important concept in the fair division. However, whether PMMS for indivisible items exists is still open. This work concentrates on PMMS by proving the existence of PMMS on linear graphs with binary valuation functions. Besides, this paper designs an algorithm to approximate PMMS in the case where different agents have identical valuations among the same items, achieving a ratio strictly greater than 0.8, which outperforms the state-of-the-art ratio of 0.781 from Kurokawa [22]. The time complexity of our FFD-based algorithm is O(mn + mlog m). [ABSTRACT FROM AUTHOR]

Among all the reactive synthesis methods, the results of the structural synthesis have the best interpretability and traceability. However, existing structural synthesis method cannot deal with real-time specifications and specifications with circular dependencies. A structural synthesis method for Programmable Logic Controller programs is proposed. First, a real-time specification pattern language, RTSPS4Syn, is proposed. Under the condition that there is no circular dependency between the specification items, the implementations of a specification item are assembled structurally from the implementation of its scope and property expression; and the programs for the specification items are concatenated according to the order of priority and dependency to obtain the synthesized program. This paper presents a method to eliminate the circular dependence of specifications, such that the synthesis approach can be applied to specifications with circular dependency. Furthermore, this paper presents an approach for setting the preset values of timers when considering tolerance on the duration of the delay. The synthesis method does not need to check the conflict and determine the nondeterministic part of the specifications. These problems are solved in existing research by constraint solving in PSPACE. [ABSTRACT FROM AUTHOR]

This paper aims to measure the operating efficiency of 22 Chinese domestic and foreign-funded life insurance companies from 2013 to 2017 and outline the path to achieve high-quality development. The DEA-Malmquist was used to evaluate the total factor productivity on the sample of 22 Chinese domestic and foreign-funded life insurance companies. A fuzzy set qualitative comparative analysis (fsQCA) was also used to analyze the configuration of determinants affecting technical efficiency. The results show that the overall operating efficiency of life insurance companies in China is relatively satisfying. The changes in total factor productivity are mainly caused by changes in technical efficiency and changes in efficiency. However, changes in scale efficiency have little effect on Chinese domestic and foreign-funded life insurance companies. There is a significant difference in the operating efficiency between Chinese domestic and foreign-funded life insurance companies. In contrast, the operating efficiency is slightly higher than that of foreign-funded life insurance companies, which is mainly reflected in the difference in pure technical efficiency. The realization path of a life insurance company's operating efficiency is primarily composed of high employee education and low overclosing ratio, high employee education and low reinsurance ratio, and all-factor positive investment. The weak employee quality and excessive overclosing are the main reasons for the low operating efficiency of some enterprises. This paper systematically analyzes the impact of the organization's internal structure on the operating efficiency of life insurance companies. Finally, based on the configuration perspective, we explain the internal logic and path of achieving better operating efficiency. In the end, we also provide decision-making references for further improving the efficient operation of life insurance companies in China. [ABSTRACT FROM AUTHOR]

This paper first reestimates the public capital stock of each China province from 1994 to 2019 by improving the computing method of the components of the perpetual inventory method (PIM). Then, it brings the public investment and public capital into the extended Cobb-Douglas production function and explores the mechanism of public investment affecting economic growth from the regional perspective. Furthermore, through the analysis of the Local Government Financing Vehicles (LGFVs) as the major investor of local public investment during the last two decades, This paper confirms the importance of complementary factors such as institutional innovation and effective management of the public infrastructure in making public investment an "effective catalyst for growth" (Kessides, 1993). [ABSTRACT FROM AUTHOR]

The non-commuting graph associated to a group has non-central elements of the graph as vertices and two elements x and y do not form an edge if and only if x y = y x. In this paper, we consider non-commuting graphs associated to dihedral and semidihedral groups. We investigate their metric properties such as center, periphery, eccentric graph, closure and interior. We also perform various types of metric identifications on these graphs. Moreover, we generate metric and metric-degree polynomials of these graphs. [ABSTRACT FROM AUTHOR]

Coal mining work has always been a high-risk job, although mining technology is now regularly very mature, many accidents still occur every year in various countries around the world, most of which are due to gas explosions, poisoning, asphyxiation and other accidents. Therefore it is important to monitor and predict both underground mine air quality. In this paper, we use the GCN spatio-temporal graph convolution method based on spectral domain for multivariate time series prediction of underground mine air environment. The correlation of these sequences is learned by a self-attentive mechanism, without a priori graph, and the adjacency matrix with an attention mechanism is created dynamically. The temporal and spatial features are learned by graph Fourier transform and inverse Fourier transform in TC module (temporal convolution) and GC module (graph convolution), respectively. Besides, the corresponding experimental predictions are performed on other public datasets. And a new loss function is designed based on the idea of residuals, which greatly improves the prediction accuracy. In addition, the corresponding experimental predictions were performed on other public datasets. The results show that this model has outstanding prediction ability and high prediction accuracy on most time-series prediction data sets. Through experimental verification, this model has high prediction accuracy for dealing with multivariate time series prediction problems, both for long-term and short-term prediction. [ABSTRACT FROM AUTHOR]

Boolean functions are fundamental bricks in the development of various applications in Cryptography and Coding theory by making benefit from the weights of related Boolean functions (Walsh spectrum). Towards this, the discrete Fourier transform (Walsh–Hadamard) plays a pivotal tool. The work in this paper is dedicated towards the algebraic and numerical degrees, together with the relationship between weights of Boolean function and their Walsh transforms. We introduce Walsh matrices and generalize them to any arbitrary Boolean function. This improves the complexity in computation of Walsh–Hadamard and Fourier transform in certain cases. We also discuss some useful results related to the degree of the algebraic normal form using Walsh–Hadamard transform. [ABSTRACT FROM AUTHOR]

The synthesis problem asks to automatically generate, if it exists, an algorithm from a specification of correct input-output pairs. In this paper, we consider the synthesis of computable functions of infinite words, for a classical Turing computability notion over infinite inputs. We consider specifications which are rational relations of infinite words, i.e., specifications defined by non-deterministic parity transducers. We prove that the synthesis problem of computable functions from rational specifications is undecidable. We provide an incomplete but sound reduction to some parity game, such that if Eve wins the game, then the rational specification is realizable by a computable function. We prove that this function is even computable by a deterministic two-way transducer. We provide a sufficient condition under which the latter game reduction is complete. This entails the decidability of the synthesis problem of computable functions, which we proved to be ExpTime-complete, for a large subclass of rational specifications, namely deterministic rational specifications. This subclass contains the class of automatic relations over infinite words, a yardstick in reactive synthesis. [ABSTRACT FROM AUTHOR]