Search

An Election is a method of selection of individuals to hold the public office in democracy. Ballot is basically a piece of paper that is used to cast vote during election. In ballot paper voting system each voter uses a ballot paper which is not shared and basically it is a paper printed with the name and symbols of the candidates. The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. In this paper, main advantages of E-voting systems for country is highlighted. For constructing E-voting systems, every countries need to do great attention to Verification and Validation requirements. In this research, E-voting scheme with face recognition using deep learning technique is proposed. The process of casting vote is accomplished by blockchain technology and blind signature mechanism. The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. • The Election is a method of selection of individuals to hold the public office in democracy. • The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. • The aim of the research is to E-voting scheme with face recognition using deep learning technique is proposed. • The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. [ABSTRACT FROM AUTHOR]

The generalized connectivity of a graph G , denoted as κ k (G) , is a generalization of the traditional connectivity and is a parameter to measure the capability of connecting multiple vertices in G. The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. This paper investigates the generalized connectivity on D S C n. We obtain the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1 , by the construction showing that there are d internally disjoint trees connecting any four arbitrary vertices of D S C n. As a corollary, one can directly obtain κ 3 (D S C n) = d. • The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. • This paper obtains the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1. • As a corollary, we also obtain κ 3 (D S C n) = d. [ABSTRACT FROM AUTHOR]

Thorup and Zwick [1] introduced the notion of approximate distance oracles, a data structure that produces for an n -vertex, m -edge weighted undirected graph G = (V , E) , distance estimations in constant query time. They presented a distance oracle of size O (k n 1 + 1 / k) that given a pair of vertices u , v ∈ V at distance d (u , v) produces in O (k) time an estimation that is bounded by (2 k − 1) d (u , v) , i.e., a (2 k − 1) -multiplicative approximation (stretch). Thorup and Zwick [1] presented also a lower bound based on the girth conjecture of Erdős. For sparse unweighted graphs (i.e., m = O ˜ (n)) the lower bound does not apply. Pǎtraşcu and Roditty [2] used the sparsity of the graph and obtained a distance oracle that uses O ˜ (n 5 / 3) space, has O (1) query time and a stretch of 2. Pǎtraşcu et al. [3] presented infinitely many distance oracles with fractional stretch factors that for graphs with m = O ˜ (n) converge exactly to the integral stretch factors and the corresponding space bound of Thorup and Zwick. It is not known, however, whether graph sparsity can help to get a stretch which is better than (2 k − 1) using only O ˜ (k n 1 + 1 / k) space. In this paper we answer this open question and prove a separation between sparse and dense graphs by showing that using sparsity it is possible to obtain better stretch/space tradeoffs than those of Thorup and Zwick. We show that for every k ≥ 2 there is a distance oracle of size O ˜ (k m 1 + 1 / k) that produces in O (k) time an estimation d ⁎ (u , v) that satisfies d (u , v) ≤ d ⁎ (u , v) ≤ (2 k − 1) d (u , v) − 4 , for k > 2 , and d (u , v) ≤ d ⁎ (u , v) ≤ 3 d (u , v) − 2 , for k = 2. Another contribution of this paper is a refined stretch analysis of Thorup and Zwick distance oracles that allows us to obtain a better understanding of this important data structure. We present simple conditions for every w ∈ V that characterize the exact scenarios in which every query that involves w produces an estimation of stretch strictly better than 2 k − 1 , even in the case of dense graphs. We complement this contribution with an experiment on real world graphs. The main finding in the experiment is that different real world graphs are likely to satisfy the required conditions and hence the stretch of Thorup and Zwick distance oracles is much better than its worst case bound in these real world graphs. • Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for general undirected graphs. • A refined stretch analysis of Thorup and Zwick Distance Oracle that characterizes several cases in which the stretch is strictly better than 2 k − 1. • An experiment on real world graphs shows that the cases characterized in the refined stretch analysis are quite frequent, and thus, in many real world graphs, the actual stretch is much better than the worst case stretch bound. [ABSTRACT FROM AUTHOR]

This paper proposes the first implementation of a self-stabilizing regular register emulated by n servers that is tolerant to both Mobile Byzantine Agents and transient failures in a round-free synchronous model. Differently from existing Mobile Byzantine Tolerant register implementations, this paper considers a weaker model where: (i) the computation of the servers is decoupled from the movements of the Byzantine agents, i.e., movements may happen before, concurrently, or after the generation or the delivery of a message, and (ii) servers are not aware of their failure state i.e., they do not know if and when they have been corrupted by a Mobile Byzantine agent. The proposed protocol tolerates (i) any finite number of transient failures, and (ii) up to f Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the Z 13 domain and it is optimal with respect to the number of servers needed to tolerate f Mobile Byzantine agents in the given model (i.e., n > 6 f when Δ = 2 δ , and n > 8 f when Δ = δ , where Δ represents the period at which the Byzantine agents move and δ is the upper bound on the communication latency). [ABSTRACT FROM AUTHOR]

By using the PoW protocol, mining pools compete to successfully mine blocks to pursue rewards. Generally, the reward from a mined block includes the fixed block subsidies and the time-varying transaction fees. The latter are offered by the senders whose transactions are packaged into blocks and are increasing with the block size being larger. However, the larger block size brings the longer latency, resulting in a smaller probability of successfully mining. Therefore, decision on the optimal block size of a block to trade off two factors above mentioned is a complex and crucial problem for the mining pools. In this paper, we model the repeated mining competition dynamics among mining pools as an evolutionary game, in which each mining pool has two strategies: following the upper bound of block size B ¯ , or selecting a block size smaller than B ¯. Because of the bounded rationality, each mining pool pursues its evolutionary stable strategy (ESS) on block size by continuous learning and adjustments during the whole mining process. A framework is built for the general evolutionary game, based on which we then explore the existence and stability of the ESSs for a case of two mining pools. Numerical experiments using the real Bitcoin data are conducted to demonstrate the theoretical results in this paper. • A framework is built for the general evolutionary game. • Based on the analysis framework, we then explore the existence and stability of the ESSs for a case of two mining pools. • Numerical experiments using the real-world Bitcoin data are conducted to demonstrate the theoretical results in this paper. [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper enriches a pre-existing decision algorithm, which in turn augmented a fragment of Tarski's elementary algebra with one-argument real functions endowed with a continuous first derivative. In its present (still quantifier-free) version, our decidable language embodies the addition of functions and multiplication of functions by scalars; the issue we address is the one of satisfiability. As regards real numbers, individual variables and constructs designating the basic arithmetic operations are available, along with comparison relators. As regards functions, we have variables of another sort, out of which compound terms are formed by means of constructs designating addition and differentiation. An array of predicates designates various relationships between functions, as well as function properties, that may hold over intervals of the real line; those are: function comparisons, strict and non-strict monotonicity / convexity / concavity, comparisons between the derivative of a function and a real-valued term. Our decision method consists in preprocessing the given formula into an equi-satisfiable quantifier-free formula of the elementary algebra of real numbers, whose satisfiability can then be checked by means of Tarski's decision method. No direct reference to functions will appear in the target formula, each function variable having been superseded by a collection of stub real variables; hence, in order to prove that the proposed translation is satisfiability-preserving, we must figure out a flexible-enough family of interpolating C 1 functions that can accommodate a model for the source formula whenever the target formula turns out to be satisfiable. With respect to the results announced in earlier papers of the same stream, a significant effort went into designing the family of interpolating functions so that it could meet the new constraints stemming from the presence of function addition (along with differentiation) among the constructs of our fragment of mathematical analysis. • A formal language RDF* concerned with differentiable real functions is proposed. • The class of differentiable functions treated is closed under addition. • The expressive power of RDF* is illustrated through a gallery of examples. • A satisfiability-preserving algorithm reducing RDF* formulas into an existential sentence of Tarskian algebra is presented. • The correctness of the reduction algorithm is reported. [ABSTRACT FROM AUTHOR]

A mixed dominating set of a graph G = (V , E) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP -hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e , and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v , a 2-approximation algorithm; 2. for w e ≥ 2 w v , inapproximability within ratio 1.3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v , inapproximability within ratio 1.1803 unless P = N P and within ratio 1.5 under UGC; 4. for w e < w v , inapproximability within ratio (1 − ϵ) ln ⁡ | V | unless P = N P for any ϵ > 0. [ABSTRACT FROM AUTHOR]

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]

Let s (n) denote the sum of digits in the binary expansion of the integer n. Hare, Laishram and Stoll (2011) studied the number of odd integers such that s (n) = s (n 2) = k , for a given integer k ≥ 1. The remaining cases that could not be treated by these authors were k ∈ { 9 , 10 , 11 , 14 , 15 }. In this paper we show that there is only a finite number of solutions for k ∈ { 9 , 10 , 11 } and comment on the difficulties to settle the two remaining cases k ∈ { 14 , 15 }. A related problem is to study the solutions of s (n 2) = 4 for odd integers. Bennett, Bugeaud and Mignotte (2012) proved that there are only finitely many solutions and conjectured that n = 13 , 15 , 47 , 111 are the only solutions. In this paper, we give an algorithm to find all solutions with fixed sum of digits value, supporting this conjecture, as well as show related results for s (n 2) = 5. [ABSTRACT FROM AUTHOR]

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we extend the maximal independent set problem to two-stage stochastic case: given an independence system associated with one deterministic weight function and a random weight function, the goal is to find two nonoverlapping independent subsets from these two stages with the maximum total weight. In this paper, we study the submodularity of three kinds of two-stage independent set problems with max-weight. When the independent set problem is a matroid constraint, we can show its submodularity. However, neither submodular nor supermodular maximization problem can be obtained for the knapsack independent set problem by designing a counterexample. At last, we show that the robust two-stage stochastic maximum-weight uniform matroid problem can be formulated as a γ -submodular problem with cardinality constraint and also give a lower bound for γ. • The submodularity of two-stage stochastic matroid problem with maximum-weight is studied using properties of bases and the circuits in matroids. • An instance of two-stage stochastic knapsack problem which is not a submodular or supermodular maximization problem is proposed. • The robust two-stage stochastic max-weight problem with cardinality constraint can be formulated as a weakly submodular maximization problem. [ABSTRACT FROM AUTHOR]

A context-free grammar with control language is a pair (G , R) where G is a context-free grammar and R is a regular set over the set of productions of G. Its language consists of all terminal words where the sequence of applied productions belongs to R. We study context-free grammars with control languages belonging to subsets of the set of regular languages. We prove that we can obtain only context-free languages if we use regular commutative and strictly locally 1-testable languages. By strictly locally k -testable, k ≥ 2 , ordered, union-free, ordered, and regular circular control languages, we have no loss in the generative power, i.e., we generate the same family which is obtained by arbitrary regular control sets. • Continuation of investigations the "power/simplification" of families of subregular languages. • Continuation of the work done by the author in the papers [3] , [4] , and [6]. • Research related to papers by Salomaa from the sixties and seventies. • Result on commutative control languages is interesting since it differs from the results for other regulation mechanisms. [ABSTRACT FROM AUTHOR]

In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walk disjointness have been proposed over the years and the validity of Menger's Theorem, as well as the complexity of related problems, have been investigated. Menger's Theorem states that the maximum number of vertex/edge disjoint paths between two vertices equals the minimum number of vertices/edges required to disconnect them. This paper introduces and investigates a type of disjointness that is only time-dependent. Two walks are said to be snapshot disjoint if they do not use edges active in the same snapshot. The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the solution size. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg, and Kumar in their seminal paper (STOC'2000), we define a snapshot Mengerian graph as a graph G for which there is no time labeling for its edges where Menger's Theorem does not hold in the context of snapshot disjointness. We then characterize Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. All our proofs work on the strict and the non-strict cases. Finally, we also present results about problems defined by similar types of disjointness, namely, multiedge disjointness and departure time disjointness. • A novel type of temporal paths disjointness. • Introduction of related parameters: maximum number of snapshot disjoint paths and minimum size of a snapshot cut. • Tight classification of related problems when parameterized by solution size. • Characterization and polynomial-time recognition of s-Mengerian graphs. • Comparison between parameters and "Mengerian" classes of graphs. [ABSTRACT FROM AUTHOR]

• C -probe graphs are graphs having stable sets N for which edges can be added to obtain a supergraph in C. • A graph G is an (r , ℓ) -graph if V (G) can be partitioned into r independent sets and ℓ cliques. • A graph G is well-covered if every maximal independent set is also maximum. • This paper studies the complexity of recognizing probe graphs for the class of (r , ℓ) -well-covered graphs. Let C be a class of graphs. A graph G = (V , E) is C -probe if V (G) can be partitioned into two sets: non-probes N and probes P , where N is an independent set and new edges may be added between some non-probe vertices such that the resulting graph is in the class C. In this case, we say that (N , P) is a C - probe partition of G. In the Unpartitioned Probe problem for a graph class C we are given a graph G and asked whether G has a C -probe partition, i.e., such a problem consist of recognizing the class of C -probe graphs. A graph G = (V , E) is an (r , ℓ) -graph when V can be partitioned into (S 1 , S 2 , ... , S r , K 1 , K 2 , ... , K ℓ) such that S 1 , S 2 , ... , S r are independent sets, and K 1 , K 2 , ... , K ℓ are cliques. A graph G is well-covered if every maximal independent set is also maximum, and it is (r , ℓ) -well-covered if it is well-covered as well as an (r , ℓ) -graph. In this paper, we study the complexity of the Unpartitioned Probe problem for the class of (r , ℓ) -well-covered graphs. We classify all but the (2 , 0) and (1 , 2) cases. [ABSTRACT FROM AUTHOR]

A vertex coloring of a graph G = (V , E) is called an exact square coloring of G if any two vertices at distance exactly 2 receive different colors. The minimum number of colors required by an exact square coloring is called the exact square chromatic number of G and is denoted by χ [ # 2 ] (G). Given a graph G and a positive integer k , the Exact Square Coloring Problem is to decide whether G admits an exact square coloring using k colors. It is known that Exact Square Coloring Problem is NP-complete for chordal graphs. In this paper, we strengthen this result by proving that this problem remains NP-complete for undirected path graphs, which is a proper subclass of chordal graphs. However, we give linear time algorithms for computing the exact square chromatic number of proper interval graphs and threshold graphs, which are proper subclasses of chordal graphs. Moreover, for a proper interval graph G , we show that χ [ # 2 ] (G) ≤ 3. We also propose a polynomial time algorithm to produce an exact square coloring of a block graph G using at most χ [ # 2 ] (G) + 1 colors. Next, we study a lower bound of χ [ # 2 ] (G). A subset S of vertices of a graph G = (V , E) is called an exact square clique of G if the distance between any two vertices in S is exactly 2. The cardinality of the maximum exact square clique of G is called the exact square clique number of G and is denoted by ω [ # 2 ] (G). Clearly, ω [ # 2 ] (G) ≤ χ [ # 2 ] (G). Given a graph G and a positive integer k , the problem of deciding whether ω [ # 2 ] (G) is at least k , is known to be NP-complete for bipartite graphs and chordal graphs. In this paper, we strengthen these results by proving that this problem remains NP-complete for undirected path graphs, perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs. We also compute the exact value of ω [ # 2 ] (G) for proper interval graphs, threshold graphs, block graphs and convex bipartite graphs. [ABSTRACT FROM AUTHOR]

Consider a Gaussian downlink between an access point with power budget P > 0 , and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit M > 0 is imposed on the number of superimposed users. For each subset S of users, its (total) power demand p (S) is a strictly increasing and nonseparable function of the effective noises and rate demands of users in S. A subset S of users is feasible if | S | ≤ M and p (S) ≤ P. The goal is to select a feasible subset S of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a (1 − 1 / e) -approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency. • The Gaussian downlink user selection problem studied in this paper is an NP-hard maximization problem. • The first 1 2 (1 − 1 / e) -approximation algorithm takes the relaxation/extraction approach. • A better algorithm utilizes partial enumeration for reducing the extraction loss, and achieves (1 − 1 / e) -approximation factor. • The paper is concluded with a summary of the general algorithmic framework and some open problems for further studies. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a subset D of vertex set V , is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set) , if the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G = (V , E) , it is NP-hard to decide whether γ (G) = γ p r (G). In this paper we settle this conjecture affirmatively. [ABSTRACT FROM AUTHOR]

The influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the non-adaptive strategies, the seeds may influence other seeds in the influence spread process and make the waste of budget. This paper considers the adaptive strategies and studies the adaptive influence maximization and adaptive stochastic influence maximization in the general feedback model. These problems select seeds adaptively, and it completes each selection after the fixed observation time-step. In this paper, we utilize the adaptive greedy to solve these problems and propose a theoretical analysis by introducing a comparative factor. In addition, we present the feasible approximation algorithm using the reverse sampling technique. Finally, we carry out experiments on three networks to show the efficiency of adaptive strategies. • We study the adaptive influence maximization problem under a general model. • We propose a comparative factor and obtain the approximation ratio of an adaptive greedy algorithm. • We not only consider the problem with cardinality constraint but also the knapsack constraint. • We conduct several experiments on three real datasets to show the effectiveness of adaptive methods. [ABSTRACT FROM AUTHOR]