A connection between Hamming codes and Heapsort is shown, namely, that they can both be derived, the first from straightforward error correcting codes and the second from a simple sorting method, using almost identica...
详细信息
A connection between Hamming codes and Heapsort is shown, namely, that they can both be derived, the first from straightforward error correcting codes and the second from a simple sorting method, using almost identical derivation processes. It is then demonstrated that the same process can work for other well-known methods. This might trigger similar derivations in the future. (C) 2013 Elsevier B.V. All rights reserved.
A constructive uniform algorithm is given for the convex matrix searching problem. The algorithm is probably optimal for the decision tree model of computation, but the actual time complexity is unknown. From previous...
详细信息
A constructive uniform algorithm is given for the convex matrix searching problem. The algorithm is probably optimal for the decision tree model of computation, but the actual time complexity is unknown. From previous results, the lower bound is Omega (n) and the upper bound is O(n alpha (n)). It is shown that the time of the algorithm is in the same asymptotic class as the minimum height decision tree. Thus, the problem of determining the asymptotic time complexity of the convex matrix searching problem is equivalent to determining the minimum decision tree height.
The reconstruction of an ultrametric tree from a distance matrix is a very frequent subproblem in clustering or reconstructing evolutionary trees, both are common problems in Bioinformatics. In his famous book, Gusfie...
详细信息
The reconstruction of an ultrametric tree from a distance matrix is a very frequent subproblem in clustering or reconstructing evolutionary trees, both are common problems in Bioinformatics. In his famous book, Gusfield presented a very simple, but not time-optimal recursive algorithm for this problem. We show that a simple modification of Gusfield's algorithm allows a time-optimal solution. (C) 2008 Elsevier B.V. All rights reserved.
We define and investigate the problem of finding all compact sets in a complete, weighted, undirected graph with n vertices. An algorithm with worst-case complexity of O(n2 log N) is given for the problem.
We define and investigate the problem of finding all compact sets in a complete, weighted, undirected graph with n vertices. An algorithm with worst-case complexity of O(n2 log N) is given for the problem.
Recently, Biham and Shamir described differential cryptanalysis: "a cryptanalytic attack which can break the Data Encryption Standard (DES) with up to eight rounds in a few minutes on a PC and can break DES with ...
详细信息
Recently, Biham and Shamir described differential cryptanalysis: "a cryptanalytic attack which can break the Data Encryption Standard (DES) with up to eight rounds in a few minutes on a PC and can break DES with up to 15 rounds faster than an exhaustive search". In this note we show that not only DES-like systems, but substitution-permutation network (SPN) cryptosystems in general which are constructed around bent function based substitution boxes (s-boxes) will be immune to Biham and Shamir's attack.
The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem o...
详细信息
The problem of single step searching a graph is investigated. We show that this problem can be solved by solving the maximum two-independent set problem. Results about solving the single step graph searching problem on special graphs are listed.
Given two n × n matrices A and B, computing their product is a classic problem. We consider a related decision problem: given three n × n matrices A, B, and C, how difficult is it to verify whether AB = C? A...
详细信息
Given two n × n matrices A and B, computing their product is a classic problem. We consider a related decision problem: given three n × n matrices A, B, and C, how difficult is it to verify whether AB = C? A method similar to Freivalds' probabilistic algorithm is used here. Our method is also similar to the constructions of Alon et al., particularly their powering construction. The constructions of Alon et al. can be used to implement Freivalds' algorithm. While Naor and Naor and Alon et al. have solved a more general problem, our algorithm yields a slightly better constant (in terms of the random bit requirement) in the general case. More importantly, our algorithm is much simpler and more direct, and it can easily be extended to make the probability of error less than any Ε with only [log2(1/Ε)] additional random bits. In Section 2, we present the simplest version of the algorithm for integer matrices. Section 3 shows how to improve the bit complexity, Section 4 extends the algorithm to matrices over finite fields, and Section 5 shows how to reduce the error probability.
For a pair of strings (S1, S2), define the suffix-prefix match of (S1, S2) to be the longest suffix of string S1 that matches a prefix of string S2. The following problem is considered in this paper. Given a collectio...
详细信息
For a pair of strings (S1, S2), define the suffix-prefix match of (S1, S2) to be the longest suffix of string S1 that matches a prefix of string S2. The following problem is considered in this paper. Given a collection of strings S1, S2,..., S(k) of total length m, find the suffix-prefix match for each of the k(k - 1) ordered pairs of strings. We present an algorithm that solves the problem in O(m + k2) time, for any fixed alphabet. Since the size of the input is OMEGA(m) and the size of the output is OMEGA(k2) this solution is optimal.
One way to state the Load Coloring Problem (LCP) is as follows. Let G = (V, E) be graph and let f : V -> (red, blue) be a 2-coloring. An edge e is an element of E is called red (blue) if both end-vertices of e are ...
详细信息
One way to state the Load Coloring Problem (LCP) is as follows. Let G = (V, E) be graph and let f : V -> (red, blue) be a 2-coloring. An edge e is an element of E is called red (blue) if both end-vertices of e are red (blue). For a 2-coloring f, let r(f)' and b(f)' be the number of red and blue edges and let mu(f)(G)= min{r(f)', b(f)'}. Let mu(G) be the maximum of mu(f)(G) over all 2-colorings. We introduce the parameterized problem k-LCP of deciding whether mu(G) >= k, where k is the parameter. We prove that this problem admits a kernel with at most 7k. Ahuja et al. (2007) proved that one can find an optimal 2-coloring on trees in polynomial time. We generalize this by showing that an optimal 2-coloring on graphs with tree decomposition of width t can be found in time O*(2(t)). We also show that either G is a Yes-instance of k-LCP or the treewidth of G is at most 2k. Thus, k-LCP can be solved in time O*(4(k)). (C) 2014 Elsevier B.V. All rights reserved.
We consider the problem of determining whether a directed graph contains a pair of vertices connected by two distinct simple paths. A straightforward implementation using n depth-first searches requires O(nm) time on ...
详细信息
We consider the problem of determining whether a directed graph contains a pair of vertices connected by two distinct simple paths. A straightforward implementation using n depth-first searches requires O(nm) time on an n-vertex, m-arc digraph;we obtain an O(n2)-time algorithm by using contraction wherever possible.
暂无评论