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]

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]

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]

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]

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]

Many decision problems concerning cellular automata are known to be decidable in the case of algebraic cellular automata, that is, when the state set has an algebraic structure and the automaton acts as a morphism. The most studied cases include finite fields, finite commutative rings and finite commutative groups. In this paper, we provide methods to generalize these results to the broader case of group cellular automata, that is, the case where the state set is a finite (possibly non-commutative) finite group. The configuration space is not even necessarily the full shift but a subshift — called a group shift — that is a subgroup of the full shift on ℤ d , for any number d of dimensions. We show, in particular, that injectivity, surjectivity, equicontinuity, sensitivity and nilpotency are decidable for group cellular automata, and non-transitivity is semi-decidable. Injectivity always implies surjectivity, and jointly periodic points are dense in the limit set. The Moore direction of the Garden-of-Eden theorem holds for all group cellular automata, while the Myhill direction fails in some cases. The proofs are based on effective projection operations on group shifts that are, in particular, applied on the set of valid space-time diagrams of group cellular automata. This allows one to effectively construct the traces and the limit sets of group cellular automata. A preliminary version of this work was presented at the conference Mathematical Foundations of Computer Science 2020. [ABSTRACT FROM AUTHOR]

We design succinct encodings of series-parallel, block-cactus and 3-leaf power graphs while supporting the basic navigational queries such as degree, adjacency and neighborhood optimally in the RAM model with logarithmic word size. One salient feature of our representation is that it can achieve optimal space even though the exact space lower bound for these graph classes is not known. For these graph classes, we provide succinct data structures with optimal query support for the first time in the literature. For series-parallel multigraphs, our work also extends the works of Uno et al. (Disc. Math. Alg. and Appl., 2013) and Blelloch and Farzan (CPM, 2010) to produce optimal bounds. [ABSTRACT FROM AUTHOR]

In our modern societies, a certain number of people do not own a car, by choice or by obligation. For some trips, there is no or few alternatives to the car. One way to make these trips possible for these people is to be transported by others who have already planned their trips. We propose to model this problem using as path-finding problem in a list edge-colored graph. This problem is a generalization of the s − t -path problem, studied by Böhmová et al. We consider two optimization functions: minimizing the number of color changes and minimizing the number of colors. We study for the previous problems, the classic complexity (polynomial-case, NP-completeness, hardness of approximation) and parameter complexity (W[2]-hardness) even in restricted cases. We also propose a lower bound for exact algorithm. On the positive side we provide a polynomial-time approximation algorithm and a FPT algorithm. [ABSTRACT FROM AUTHOR]

Given a set of h pairwise disjoint convex polygonal obstacles in the plane, defined with n vertices, we preprocess and compute one routing table at each vertex in a subset of vertices of . For routing a packet from any vertex s ∈ to any vertex t ∈ , our scheme computes a routing path with a multiplicative stretch 1 + and an additive stretch 2 k ℓ , by consulting routing tables at only a subset of vertices along that path. Here, k is the number of obstacles of the routing path intersects, and ℓ depends on the geometry of obstacles in . During the preprocessing phase, we construct routing tables of size O (n + h 3 2 polylog (h )) in O (n + h 3 2 polylog (h )) time, where < 1 is an input parameter. [ABSTRACT FROM AUTHOR]

Consider the problem of finding a point furthest from x for each point x in a metric space ([ n ] , d) , where [ n ] = { 1 , 2 , ... , n }. We prove this problem to have a deterministic O (n) -time 1 / 3 -approximation algorithm. As a corollary, the maximum spanning tree problem in metric spaces has a deterministic O (n) -time 1 / 3 -approximation algorithm. We also give a Monte Carlo O (n 1. 5 log n) -time algorithm outputting, for each x ∈ [ n ] , a point y x ∈ [ n ] satisfying d (x , y x) ≥ Δ / 2 , where Δ ≡ max x , y ∈ [ n ] d (x , y). As a corollary, we have a Monte Carlo O (n 1. 5 log n) -time algorithm for finding a spanning tree of weight at least (1 / 2 − o (1)) Δ n in ([ n ] , d). [ABSTRACT FROM AUTHOR]

Processor fault diagnosis is intended to identify faulty processors of a multicomputer system, guaranteeing its high reliability and availability. The g -good-neighbor conditional diagnosability is a novel fault diagnosis method for various networks. Under the PMC model and comparison model, the g -good-neighbor conditional diagnosabilities of hypermesh optical interconnection networks are determined, respectively. Directly applying the results, the g -good-neighbor conditional diagnosabilities of hypercubes are derived under the PMC and comparison models. [ABSTRACT FROM AUTHOR]

Let p be an odd prime number, q = p m for a positive integer m , let q be the finite field with q elements and ω be a primitive element of q . We first give an orthogonal decomposition of the ring R = q + ν q , where ν 2 = a 3 , and a = ω 2 l for a fixed integer l. In addition, Galois dual of a linear code over R is discussed. Meanwhile, constacyclic codes and cyclic codes over the ring R are investigated as well. Remarkably, we obtain that if linear codes and are a complementary pair, then the code and the dual code ⊥ E of are equivalent to each other. [ABSTRACT FROM AUTHOR]

We consider words over a binary alphabet. A word w is overlap-free if it does not have factors (blocks of consecutive letters) of the form u v u v u for nonempty u. Let M (w) denote the number of positions that are middle positions of squares (of the form u u) in w. We show that for overlap-free binary words, 2 M (w) ≤ | w | + 3 , and that there are infinitely many overlap-free binary words for which 2 M (w) = | w | + 3. [ABSTRACT FROM AUTHOR]

We show that the equivalence, unambiguity, and sequentiality problems are decidable for finitely ambiguous max-plus tree automata. A max-plus tree automaton is a weighted tree automaton over the max-plus semiring. A max-plus tree automaton is called finitely ambiguous if the number of accepting runs on every tree is bounded by a global constant and it is called unambiguous if there exists at most one accepting run on every tree. For the equivalence problem, we show that for two finitely ambiguous max-plus tree automata, it is decidable whether both assign the same weight to every tree. For the unambiguity and sequentiality problems, we show that for every finitely ambiguous max-plus tree automaton, both the existence of an equivalent unambiguous automaton and the existence of an equivalent deterministic automaton are decidable. [ABSTRACT FROM AUTHOR]

The class of Boolean combinations of tree languages recognized by deterministic top-down tree automata (also known as deterministic root-to-frontier automata) is studied. The problem of determining for a given regular tree language whether it belongs to this class is open. We provide some progress by two results: First, a characterization of this class by a natural extension of deterministic top-down tree automata is presented, and as an application we obtain a convenient method to show that certain regular tree languages are outside this class. In the second result, it is shown that, for fixed k , it is decidable whether a regular tree language is a Boolean combination of k tree languages recognized by deterministic top-down tree automata. [ABSTRACT FROM AUTHOR]