Search

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

We push a little further the study of two recent characterizations of almost perfect nonlinear (APN) functions. We state open problems about them, and we revisit in their perspective a well-known result from Dobbertin on APN exponents. This leads us to a new result about APN power functions and more general APN polynomials with coefficients in a subfield \begin{document}$ \mathbb{F}_{2^k} $\end{document} , which eases the research of such functions. It also allows to construct automatically many differentially uniform functions from them (this avoids calculations for proving their differential uniformity as done in a recent paper, which are tedious and specific to each APN function). In a second part, we give simple proofs of two important results on Boolean functions, one of which deserves to be better known but needed clarification, while the other needed correction.

Graph states are present in quantum information and found applications ranging from quantum network protocols (like secret sharing) to measurement based quantum computing. In this paper, we extend the notion of graph states, which can be regarded as pure quantum graph states, or as homogeneous quadratic Boolean functions associated to simple undirected graphs, to quantum states based on mixed graphs (graphs which allow both directed and undirected edges), obtaining mixed quantum states, which are defined by matrices associated to the measurement of homogeneous quadratic Boolean functions in some (ancillary) variables. In our main result, we describe the extended graph state as the sum of terms of a commutative subgroup of the stabilizer group of the corresponding mixed graph with the edges' directions reversed.

In this paper, a new class of generalized cyclotomic binary sequences with period \begin{document}$ 4p^n $\end{document} is proposed. These sequences are almost balanced, and the explicit formulas of their linear complexity and autocorrelation are presented.

Recently, Ivanov et al. proposed a new approach to construct code-based cryptosystems, namely the \begin{document}$ {\sf IKKR} $\end{document} public-key encryptions (PKE) in the International Workshop on Code-Based Cryptography (CBCrypto 2020) [ 9 ]. Unlike the usual construction in code-based encryption schemes which has restrictions on the Hamming weight of the error introduced into the ciphertext, the \begin{document}$ {\sf IKKR} $\end{document} approach allows error vectors of arbitrary weight being introduced into the ciphertext. Using this new approach, Ivanov et al. constructed two cryptosystems, namely the modified and the upgraded \begin{document}$ {\sf IKKR} $\end{document} -PKE. This paper aims to discuss the practical security of the \begin{document}$ {\sf IKKR} $\end{document} -PKE. In particular, we describe the weaknesses in the design of the public key used in the \begin{document}$ {\sf IKKR} $\end{document} -PKE. We exploit such weaknesses and propose two attacks to recover the plaintext in the \begin{document}$ {\sf IKKR} $\end{document} -PKE. The approach of our first attack is similar to the LCKN attack [ 12 ], whilst our second attack is more efficient than the LCKN attack. Our experimental results show that we can recover the plaintext from a given ciphertext in less than 176 milliseconds for schemes based on random Goppa codes and BCH codes.

Building upon the application of flags to network coding introduced by Liebhold, Nebe, and Vazquez-Castro, we develop a variant of this coding technique that uses degenerate flags. The information set is a metric affine space isometric to the space of upper triangular matrices endowed with the flag rank metric. This suggests the development of a theory for flag rank metric codes in analogy to the rank metric codes used in linear subspace coding., Updated acknowledgements

We consider relationships between Vandermonde sets and hyperovals. Hyperovals are Vandermonde sets, but in general, Vandermonde sets are not hyperovals. We give necessary and sufficient conditions for a Vandermonde set to be a hyperoval in terms of power sums. Therefore, we provide purely algebraic criteria for the existence of hyperovals. Furthermore, we give necessary and sufficient conditions for the existence of hyperovals in terms of \begin{document}$ g $\end{document} -functions, which can be considered as an analog of Glynn's Theorem for \begin{document}$ o $\end{document} -polynomials. We also get some important applications to Niho bent functions.

Absorbing sets are combinatorial structures in the Tanner graphs of low-density parity-check (LDPC) codes that have been shown to inhibit the high signal-to-noise ratio performance of iterative decoders over many communication channels. Absorbing sets of minimum size are the most likely to cause errors, and thus have been the focus of much research. In this paper, we determine the sizes of absorbing sets that can occur in general and left-regular LDPC code graphs, with emphasis on the range of \begin{document}$ b $\end{document} for a given \begin{document}$ a $\end{document} for which an \begin{document}$ (a,b) $\end{document} -absorbing set may exist. We identify certain cases of extremal absorbing sets that are elementary, a particularly harmful class of absorbing sets, and also introduce the notion of minimal absorbing sets which will help in designing absorbing set removal algorithms.

With view to applications to harmonic and stochastic analysis of infinite network/graph models, we introduce new tools for realizations and transforms of positive definite kernels (p.d.) \begin{document}$ K $\end{document} and their associated reproducing kernel Hilbert spaces. With this we establish two kinds of factorizations: (i) Probabilistic: Starting with a positive definite kernel \begin{document}$ K $\end{document} we analyze associated Gaussian processes \begin{document}$ V $\end{document} . Properties of the Gaussian processes will be derived from certain factorizations of \begin{document}$ K $\end{document} , arising as a covariance kernel of \begin{document}$ V $\end{document} . (ii) Geometric analysis: We discuss families of measure spaces arising as boundaries for \begin{document}$ K $\end{document} . Our results entail an analysis of a partial order on families of p.d. kernels, a duality for operators and frames, optimization, Karhunen–Loeve expansions, and factorizations. Applications include a new boundary analysis for the Drury-Arveson kernel, and for certain fractals arising as iterated function systems; and an identification of optimal feature spaces in machine learning models.

In this paper, we propose cryptanalytic results on two lightweight stream ciphers: Fountain v1 and Lizard. The main results of this paper are the followings: \begin{document}$ - $\end{document} We propose a zero-sum distinguisher on reduced round Fountain v1. In this context, we study the non-randomness of the cipher with a careful selection of cube variables. Our obtained cube provides a zero-sum on Fountain v1 till \begin{document}$ 188 $\end{document} initialization rounds and significant non-randomness till \begin{document}$ 189 $\end{document} rounds. This results in a distinguishing attack on Fountain v1 with \begin{document}$ 189 $\end{document} initialization rounds. \begin{document}$ - $\end{document} Further, we find that the same cipher has a weakness against conditional Time-Memory-Data-Tradeoff (TMDTO). We show that TMDTO attack using sampling resistance has online complexity \begin{document}$ 2^{110} $\end{document} and offline complexity \begin{document}$ 2^{146} $\end{document} . \begin{document}$ - $\end{document} Finally, we revisit the Time-Memory-Data-Tradeoff attack on Lizard by Maitra et al. (IEEE Transactions on Computers, 2018) and provide our observations on their work. We show that instead of choosing any random string, some particular strings would provide better results in their proposed attack technique.

Recently, Borello and Jamous have investigated some lower bounds on the dimension and minimum distance for dihedral codes, in analogy with the theory of BCH codes. In this paper, we extend some of their results to split metacyclic codes, that is, codes over semidirect products of cyclic groups.

Regev (2005) introduced the learning with errors (LWE) problem and showed a quantum reduction from a worst case lattice problem to LWE. Building on the work of Peikert (2009), a classical reduction from the gap shortest vector problem to LWE was obtained by Brakerski et al. (2013). A concrete security analysis of Regev's reduction by Chatterjee et al. (2016) identified a huge tightness gap. The present work performs a concrete analysis of the tightness gap in the classical reduction of Brakerski et al. It turns out that the tightness gap in the Brakerski et al. classical reduction is even larger than the tightness gap in the quantum reduction of Regev. This casts doubts on the implication of the reduction to security assurance of practical cryptosystems.

In this paper, we first introduce a class of quartic Boolean functions. And then, the construction of weightwise perfectly balanced Boolean functions on \begin{document}$ 2^m $\end{document} variables are given by modifying the support of the quartic functions, where \begin{document}$ m $\end{document} is a positive integer. The algebraic degree, the weightwise nonlinearity, and the algebraic immunity of the newly constructed weightwise perfectly balanced functions are discussed at the end of this paper.

What does it mean today to study a problem from a computational point of view? We focus on parameterized complexity and on Column 16 “Graph Restrictions and Their Effect” of D.S. Johnson’s Ongoing guide, where several puzzles were proposed in a summary table with 30 graph classes as rows and 11 problems as columns. Several of the 330 entries remain unclassified into Polynomial or NP -complete after 35 years. We provide a full dichotomy for the Steiner Tree column by proving that the problem is NP -complete when restricted to Undirected Path graphs. We revise Johnson’s summary table according to the granularity provided by the parameterized complexity for NP -complete problems.

Given an undirected connected graph G = ( V , E ) , the minimum linear arrangement problem (MinLA) consists in determining a permutation π ≔ ( π 1 , … , π n ) of the node-set V = { 1 , … , n } , which minimizes the sum of edge costs | π i − π j | over all edges { i , j } ∈ E . We introduce a compact quadratic formulation, prove its correctness, and generate new mixed-integer linear formulations that require a very small number of variables and constraints. The idea behind the way we model permutations allows the development of strong valid constraints to strengthen the new formulations. We also adapt some cutting plane procedures from the literature to one of the new models. Computational experiments with benchmark and new instances are very encouraging and improve state-of-the-art solution approaches from the literature.

We characterize the optimal solution to the linear programming relaxation of the standard formulation for the minimum satisfiability problem. We give a O ( n m 2 ) combinatorial algorithm to solve the fractional version of the minimum satisfiability problem optimally where n ( m ) is the number of variables (clauses). As a by-product, we obtain a 2 ( 1 − 1 ∕ 2 k ) approximation algorithm for the minimum satisfiability problem where k is the maximum number of literals in any clause.

In communication networks, the existence of fractional factors can be characterized as the feasibility of data transmission. When some nonadjacent nodes with each other are damaged and a special channel is assigned, the possibility of data transmission in a communication network is equivalent to the existence of fractional ID-factor-critical covered graph. As a consequence, the existence of fractional ID- [ a , b ] -factor-critical covered graph plays a key role in studying data transmissions of communication networks. Neighborhood and minimum degree of a graph or a network are often used to measure the vulnerability and robustness of a graph or a network, which are two important parameters considered in network design. In this article, we mainly investigate the relationship between neighborhood of independent set, minimum degree and the fractional ID- [ a , b ] -factor-critical covered graph, and acquire a neighborhood of independent set and minimum degree condition for a graph being fractional ID- [ a , b ] -factor-critical covered, which is a generalization of the previous results.

Bitprobe complexity of the static membership problem has been widely investigated since Burhman et al. (2000) studied the worst-case bounds for a whole range of membership problems. Though tremendous progress has been made in recent years, as is evident from the remarkable papers due to Alon and Feige (2009) [1] , Viola (2012) [8] , and Lewenstein et al. (2014), among others, Nicholson et al. (2013) [5] in their survey of the state of the art of the area noted that even the first non-trivial scenario of two probe adaptive schemes storing two elements of the universe is not completely settled, in that the lower bound for this problem is still open. We propose a proof (Kesh and Sharma, 2019) [3] for the lower bound for the same problem, but for a restricted class of schemes. We believe that this proof makes progress over the ideas proposed by Radhakrishnan et al. (2001, 2010) towards the proof. It is our belief that the single restriction imposed on the general class of schemes towards our proof faithfully captures the dependencies among the elements that share the same bit in the datastructure, and we hope that the general lower bound proof can be developed using similar ideas.

We use the hypergraph container theory of Balogh--Morris--Samotij and Saxton--Thomason to obtain general rectilinear approximations and volume estimates for sequences of bodies closed under certain families of projections. We give a number of applications of our results, including a multicolour generalisation of a theorem of Hatami, Janson and Szegedy on the entropy of graph limits. Finally, we raise a number of questions on geometric and analytic approaches to containers., Comment: 25 pages, author accepted manuscript, to appear in Journal of Graph Theory

Diagnosis plays an important role in measuring the reliability of an interconnection network, and the diagnosability of interconnection networks has been widely investigated. For a system G , Zhang et al. introduced h -extra conditional diagnosability, denoted by t h ( G ) , which is a novel measure of diagnosability. In this paper, several new structural properties of balanced hypercubes have been derived. Based on these properties, the 3-extra conditional diagnosability of an n -dimensional balanced hypercube is determined to be t 3 ( B H n ) = 4 n − 1 for n ≥ 5 under the MM ∗ model.

Boolean functions with five-valued Walsh spectra (shortened as five-valued functions) and semi-bent functions are two classes of Boolean functions with high nonlinearity. They have useful applications in cryptography and communications. In this paper, we first present the construction of resilient five-valued functions by modifying the support of Rothaus’s bent function. And then, we give the method of constructing resilient semi-bent functions. At the same time, the number of the newly constructed resilient semi-bent functions is determined. Lastly, we give the construction of resilient semi-bent functions with maximal algebraic degree.

Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in both pure and applied mathematics. In particular, the security of the so-called multivariate public-key cryptosystems, such as HFE of Patarin and UOV of Kipnis et al., is based on the postulated hardness of solving quadratic polynomial systems over a finite field. Lokshtanov et al. (2017) were the first to introduce a probabilistic algorithm that, in the worst-case, solves a Boolean polynomial system in time O ∗ ( 2 δ n ) , for some δ ∈ ( 0 , 1 ) depending only on the degree of the system, thus beating the brute-force complexity O ∗ ( 2 n ) . Later, Bjorklund et al. (2019) and then Dinur (2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient δ . We survey the theory behind these probabilistic algorithms, and we illustrate the results that we obtained by implementing them in C. In particular, for random quadratic Boolean systems, we estimate the practical complexities of the algorithms and their probabilities of success as their parameters change.

We present well known properties related to the topology of Steiner minimal trees and to the geometric position of Steiner points, and investigate their application in the exact algorithms that have been proposed for the Euclidean Steiner problem. We discuss the difficulty in the application of properties that were very successfully applied to solve the problem in the plane, when the dimension of the space increases, and point out that the application of some geometric conditions for Steiner points is hindered when the well known implicit enumeration scheme proposed by Smith in 1992 is considered. Finally, we mention mathematical-optimization methods as a direction to explore in the search for good formulations of inequalities that would allow the application of these restrictive geometric conditions.

The recent FLIP cipher is an encryption scheme described by Meaux et al. at EUROCRYPT 2016. In the FLIP cipher, the input to the Boolean function used as a filter function has constant Hamming weight equal to the weight of the secret key. Weightwise perfectly balanced Boolean functions, which can be used in the FLIP cipher, only exist on 2 m variables, while weightwise almost perfectly balanced Boolean functions can exist on an arbitrary number of variables. In this paper, we first introduce a class of quadratic Boolean functions on n variables, where n is a positive integer. We then propose a construction of weightwise almost perfectly balanced Boolean functions on n variables by modifying the support of the quadratic Boolean functions.

In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by Krivelevich [SIAM J. Disc. Math. 32 1 (2018)]. Here, we show that the problem of finding a large induced subgraph that is an expander can be reduced to the simpler problem of finding a topological minor that is an expander. Our proof is constructive, which is helpful in an algorithmic setting. We also show that every large subgraph of an expander graph contains a large subgraph which is itself an expander., 16 pages, 8 figures

For fixed non-negative integers $k$, $t$, and $n$, with $t < k$, a $k_t$-Dyck path of length $(k+1)n$ is a lattice path that starts at $(0, 0)$, ends at $((k+1)n, 0)$, stays weakly above the line $y = -t$, and consists of steps from the step-set $\{(1, 1), (1, -k)\}$. We enumerate the family of $k_t$-Dyck paths by considering the number of down-steps at a height of $i$ modulo $k$. Given a tuple $(a_1, a_2, \ldots, a_k)$ we find an exact enumeration formula for the number of $k_t$-Dyck paths of length $(k+1)n$ with $a_i$ down-steps at a height of $i$ modulo $k$, $1 \leq i \leq k$. The proofs given are done via bijective means or with generating functions.

The classes of tree permutations and forest permutations were defined by Acan and Hitczenko (2016). We study random permutations of a given length from these classes, and in particular the number of occurrences of a fixed pattern in one of these random permutations. The main results show that the distributions of these numbers are asymptotically normal. The proof uses representations of random tree and forest permutations that enable us to express the number of occurrences of a pattern by a type of $U$-statistics; we then use general limit theorems for the latter., 30 pages. v2 important typo corrected

In this paper we first study $k \times n$ Youden rectangles of small orders. We have enumerated all Youden rectangles for a range of small parameter values, excluding the almost square cases where $k = n-1$, in a large scale computer search. In particular, we verify the previous counts for $(n,k) = (7,3), (7,4)$, and extend this to the cases $(11,5), (11,6), (13,4)$ and $(21,5)$. For small parameter values where no Youden rectangles exist, we also enumerate rectangles where the number of symbols common to two columns is always one of two possible values, differing by 1, which we call \emph{near Youden rectangles}. For all the designs we generate, we calculate the order of the autotopism group and investigate to which degree a certain transformation can yield other row-column designs, namely double arrays, triple arrays and sesqui arrays. Finally, we also investigate certain Latin rectangles with three possible pairwise intersection sizes for the columns and demonstrate that these can give rise to triple and sesqui arrays which cannot be obtained from Youden rectangles, using the transformation mentioned above.

We study the probabilistic properties of reliable networks of minimum costs in d -dimensional Euclidean space, with reliability in terms of k -edge-connectivity in graphs. We show that this problem fits into Yukich’s framework for Euclidean functionals for arbitrary k , dimension d and distant-power gradient p with p d . With this framework, several theorems on convergence and concentration of the value of optimal solutions follow. These results are then extended to optimal k -edge-connected power assignment graphs, where we assign transmit power to nodes, and two nodes are connected if they both have sufficient transmit power. This variant models wireless networks. Finally, we devise a partitioning heuristic to find approximate solutions quickly, and we analyze its performance in the framework of smoothed analysis.

Cops and robber is a two player turn-based game played on a graph where cops try to capture the robber. The cop number of a graph is the minimum number of cops required to capture the robber. We consider two variants of this game, namely cops and attacking robber and lazy cops and robber. In cops and attacking robber version, the robber can attack a cop and remove that cop from the game, whereas in lazy cops and robber version only one cop is allowed to move on a cop’s turn. We investigate the cop number of various grids (planar, cylindrical, toroidal and high dimension) and hypercubes for these variants.

Connectivity and diagnosability are two important metrics for reliability of multiprocessor systems. As generalizations of traditional connectivity, g -good neighbor connectivity (resp., diagnosability) and g -component connectivity (resp., diagnosability) are significant parameters to characterize invulnerability of multiprocessor systems. In this paper, we determine that g -good neighbor connectivity of DQcube ( D Q n ) , a compound graph based on disc-ring and hypercube, is κ g ( D Q n ) = 2 g ( n + 1 − g ) for 0 ≤ g ≤ n − 2 . Immediately, we show that g -good neighbor diagnosability of D Q n under PMC model and MM ∗ model is t g ( D Q n ) = 2 g ( n + 2 − g ) − 1 . In addition, we prove that ( g + 1 ) -component connectivity of D Q n is c κ g + 1 ( D Q n ) = − 1 2 g 2 + ( n + 1 2 ) g + 1 , and ( g + 1 ) -component diagnosability of D Q n under PMC model and MM ∗ model is c t g + 1 ( D Q n ) = − 1 2 g 2 + ( n − 1 2 ) g + n + 1 for 1 ≤ g ≤ n − 2 .

Unidirectional star graphs, the star graph interconnection networks with simplex unidirectional links, can be used in the area of parallel and distributed computing. The 1-good-in-neighbor connectivity, the 1-good-out-neighbor connectivity, and the 1-good-neighbor connectivity are more accurate network reliability indices than the classical connectivity. In this paper, we first give lower bounds on the cardinalities of the out-neighborhood and the in-neighborhood of a vertex subset of a unidirectional star graph and then determine the 1-good-in-neighbor connectivity, the 1-good-out-neighbor connectivity, and the 1-good-neighbor connectivity of unidirectional star graphs.

In this paper we provide a deterministic fully polynomial time approximation scheme (FPTAS) for counting two-rowed contingency tables that is faster than any either deterministic or randomized approximation scheme for this problem known to date. Our FPTAS is derived via a somewhat sophisticated usage of the method of K -approximation sets and functions introduced by Halman et al. (2009).

The hypercube cut number S ( d ) is the minimum number of hyperplanes in the d -dimensional Euclidean space that slice all the edges of the d -cube. The determination of S ( d ) in dimensions 5, 6, and 7, is one of the Victor Klee’s unresolved problems presented in one of his invited talks on problems from discrete geometry. The value of S ( d ) is unknown for d ≥ 7 , but for d ≤ 3 it is trivial to show S ( d ) = d . In the late nineteen eighties, Emamy-K has shown S ( 4 ) = 4 via two different proofs. More than a decade later, Sohler and Ziegler obtained a computational proof of S ( 5 ) = 5 that took about two months of CPU computing time. From S ( 5 ) = 5 it can be verified that S ( 6 ) = 5 . A short mathematical proof for d = 5 remains to be a challenging problem that also leads one to the insight of the still open 7-dimensional problem. In this article we present a vertex coloring approach on the hypercube that gives a simplified proof for d = 4 and also helps toward a short mathematical proof for d = 5 , free of computer computations.

Given an undirected graph G = ( V , E ) and a positive integer k ∈ 1 , … , | V | , we initiate the combinatorial study of stable sets of cardinality exactly k in G . Our aim is to instigate the polyhedral investigation of the convex hull of fixed cardinality stable sets, inspired by the rich theory on the classical structure of stable sets. We introduce a large class of valid inequalities to the natural integer programming formulation of the problem. We also present simple combinatorial relaxations based on computing maximum weighted matchings, which yield dual bounds towards finding minimum-weight fixed cardinality stable sets, and particular cases which are solvable in polynomial time.

Network interdiction problems by upgading critical edges/nodes have important applications to reduce the infectivity of the COVID-19. A network of confirmed cases can be described as a rooted tree that has a weight of infectious intensity for each edge. Upgrading edges (nodes) can reduce the infectious intensity with contacts by taking prevention measures such as disinfection (treating the confirmed cases, isolating their close contacts or vaccinating the uninfected people). We take the sum of root-leaf distance on a rooted tree as the whole infectious intensity of the tree. Hence, we consider the sum of root-leaf distance interdiction problem by upgrading edges/nodes on trees (SDIPT-UE/N). The problem (SDIPT-UE) aims to minimize the sum of root-leaf distance by reducing the weights of some critical edges such that the upgrade cost under some measurement is upper-bounded by a given value. Different from the problem (SDIPT-UE), the problem (SDIPT-UN) aims to upgrade a set of critical nodes to reduce the weights of the edges adjacent to the nodes. The relevant minimum cost problem (MCSDIPT-UE/N) aims to minimize the upgrade cost on the premise that the sum of root-leaf distance is upper-bounded by a given value. We develop different norms to measure the upgrade cost. Under weighted Hamming distance, we show the problems (SDIPT-UE/N) and (MCSDIPT-UE/N) are NP-hard by showing the equivalence of the two problems and the 0–1 knapsack problem. Under weighted \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$l_1$$\end{document}l1 norm, we solve the problems (SDIPT-UE) and (MCSDIPT-UE) in O(n) time by transforimg them into continuous knapsack problems. We propose two linear time greedy algorithms to solve the problem (SDIPT-UE) under unit Hamming distance and the problem (SDIPT-UN) with unit cost, respectively. Furthermore, for the the minimum cost problem (MCSDIPT-UE) under unit Hamming distance and the problem (MCSDIPT-UN) with unit cost, we provide two \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document}O(nlogn) time algorithms by the binary search methods. Finally, we perform some numerical experiments to compare the results obtained by these algorithms.

We prove that every K–subadditive set–valued map weakly K–upper bounded on a “large” set (e.g. not null–finite, not Haar–null or not a Haar–meager set), as well as any K–superadditive set–valued map K–lower bounded on a “large” set, is locally K–lower bounded and locally weakly K–upper bounded at every point of its domain.

In network construction/restoration problems introduced in Averbakh and Pereira (IIE Trans 44(8):681–694, 2012; Eur J Oper Res 244:715–729, 2015), a server (construction crew) builds edges of a given network starting from a given vertex (the depot), with a constant construction speed. The server can travel within the already constructed part of the network with a speed that is incomparably faster than the construction speed. The recovery time of a vertex is the time when the vertex becomes connected to the depot by an already constructed path. Due dates and/or weights are associated with vertices. It is required to find an optimal construction schedule that minimizes the total weighted recovery time or the maximum lateness of the vertices. Both problems are known to be polynomially solvable on trees and NP-hard on general networks. We prove that both problems are NP-hard even on so simple extensions of trees as cactuses, and discuss some polynomially solvable cases.

A tensegrity graph is a graph with edges labeled as bars, cables and struts. A realization of a tensegrity graph T is a pair ( T , p ) , where p maps the vertices of T into R d for some d ≥ 1 . The realization is globally rigid if any realization ( T , q ) in R d in which the bars have the same length and the cables and struts are not longer and not shorter, respectively, is an isometric image of ( T , p ) . A tensegrity graph is weakly globally rigid in R d if it has a generic globally rigid realization in R d , and strongly globally rigid in R d if every generic realization in R d is globally rigid. In this paper we give a necessary condition for weak global rigidity in R d and prove that in the d = 1 case the same condition is also sufficient. In particular, our results imply that a tensegrity graph has a generic globally rigid realization in R 1 if and only if it has a generic universally rigid realization in R 1 . We also show that recognizing strongly globally rigid tensegrity graphs in R d is co-NP-hard for all d ≥ 1 .

We consider a constrained version of the shortest path problem on the complete graphs whose edges have independent random lengths and costs. We establish the asymptotic value of the minimum length as a function of the cost-budget within a wide range.

A legal dominating sequence of a graph is an ordered dominating set of vertices where each element dominates at least another one not dominated by its predecessors in the sequence. The length of a largest legal dominating sequence is called Grundy domination number. In this work, we introduce a generalized version of the Grundy domination problem. We explicitly calculate the corresponding parameter for paths and web graphs. We propose integer programming formulations for the new problem, find families of valid inequalities and perform extensive computational experiments to compare the formulations as well as to test these inequalities as cuts in a branch-and-cut framework. We also design and evaluate the performance of a heuristic for finding good initial lower and upper bounds and a tabu search that improves the initial lower bound. The test instances include randomly generated graphs, structured graphs, classical benchmark instances and two instances from a real application. Our approach is exact for graphs with 20–50 vertices and provides good solutions for graphs up to 10 000 vertices.

Given a binomial probability distribution on the n-dimensional Boolean cube, the complexity of implementation of Boolean functions by straight line programs with conditional stop is considered. The order, as n → ∞, of the average-case complexity of almost all n-place Boolean functions is established.

The complexity of implementation of a threshold symmetric n-place Boolean function with threshold k = O(1) via circuits over the basis {∨, ∧} is shown not to exceed 2 log2 k ⋅ n + o(n). Moreover, the complexity of a threshold-2 function is proved to be 2n + Θ( $\begin{array}{} \sqrt n \end{array} $ ), and the complexity of a threshold-3 function is shown to be 3n + O(log n), the corresponding lower bounds are put forward.

In this note we resolve three conjectures from Dehmer et al. (2019) on the comparison of distance measures based on the graph spectra, by constructing families of counterexamples and using computer search. In addition, we prove other results and conditions under which the conjectures hold true.

A communication network can be considered to be highly vulnerable to disruption if the failure of few members (nodes or links) can result in no member’s being able to communicate with very many others. These communication networks can be modeled through graphs, and we have several graph-theoretic parameters (viz., connectivity, edge-connectivity, tenacity etc.,) to describe the stability of graphs. But, these parameters are not sufficient to study stability of graphs. This leads to the concept of integrity of a graph. The integrity of a graph will consider both the damage and the maximum possible capacity of communication corresponding to the maximum damage to the network. Therefore, we discuss the integrity of total transformation graphs which can help us to reconstruct the given network in such a way that it is more stable than the earlier one. If the network is modeled through total transformation graphs, then there will be increase in the number of nodes and links between the nodes in the obtained network which automatically cause the increase in the stability of the network. In this paper, we obtain the integrity of total transformation graphs of some special class of graphs. Further, we present bounds of integrity of some total transformation graphs of a graph in terms of number of vertices, number of edges and integrity of some derived graph appears as induced subgraph. The expression for integrity of total graph of cycle which was given by Qingfang Ye contained an error. We give correct version of it. In addition, we compute integrity of book graphs.