The 2-intersection number of paths and bounded-degree trees

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2-intersection number θ₂(G) of a graph G is the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way using t elements is between (t² - 19t + 4)/4 and (t² - t + 6)/4, making θ₂(P_n) asymptotic to 2√n. We also show the existence of a constant c depending on ? such that, for any tree T with maximum degree at most d, θ₂(T) ≤ c(√n)^1+?. When the maximum degree is not bounded, there is an n-vertex tree T with θ₂(T) > .945n^2/3. © 1995 John Wiley & Sons, Inc.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

UPPER BOUNDS ON THE LOWER OPEN PACKING NUMBER OF A TREE

Abstract

Let G be a graph and let v be a vertex of G. The open neigbourhood N(v) of v is the set of all vertices adjacent with v in G. An open packing of G is a set of vertices whose open neighbourhoods are pairwise disjoint. The lower open packing number of G, denoted ρ^° _L(G), is the minimum cardinality of a maximal open packing of G while the (upper) open packing number of G, denoted ρ^°(G), is the maximum cardinality among all open packings of G. It is known (see [7]) that if G is a connected graph of order n ≥3, then ρ^°(G) ≤ 2n/3 and this bound is sharp (even for trees). As a consequence of this result, we know that ρ^° _L(G) ≤ 2n/3. In this paper, we improve this bound when G is a tree. We show that if G is a tree of order n with radius 3, then ρ^° _L(G) ≤ n/2 + 2 √n-1, and this bound is sharp, while if G is a tree of order n with radius at least 4, then ρ^° _L(G) is bounded above by 2n/3—O√n).     

General symbolic powers: A homological point of view

Let I be an ideal of a Noetherian ring R and let S be a multiplicatively closed subset of R. We define the n-th (S)-symbolic power of 7 as S(Iⁿ) = IⁿR_s ∩R. The purpose of this paper is to compare the topologies defined by the adic {I_n}_n≤0 and the (S)-symbolic filtration {S(Iⁿ)}n≥o using the direct system {Extⁱ _R(R/Iⁿ,R)}_n≥0     

Inversion of the Radon transform with incomplete data

The Radon transform R(p, θ), θ∈S^n?1, p∈?¹, of a compactly supported function f(x) with support in a ball B_a of radius a centred at the origin is given for all $ \theta \in \mathop {S^{n - 1} }\limits^\tilde $, where $ \mathop {S^{n - 1} }\limits^\tilde $ is an open set on S^n?1, and all p∈(? ∞, ∞), n≥2. An approximate formula is given to calculate f(x) from the given data.     

On the maximum number of edges in a c4-free subgraph of qn

For the maximum number f(n) of edges in a C₄-free subgraph of the n-dimensional cube-graph Q_n we prove f(n) ≥ 1/2(n +√n)2^n?1 for n = 4^r, and f(n) ≥ 1/2(n +0.9√n)2^n?1 for all n ≥ 9. This disproves one version of a conjecture of P. Erdos. © 1995 John Wiley & Sons, Inc.     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

Equitable coloring of random graphs

An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most one. The least positive integer k for which there exists an equitable coloring of a graph G with k colors is said to be the equitable chromatic number of G and is denoted by χ₌(G). The least positive integer k such that for any k′ ≥ k there exists an equitable coloring of a graph G with k′ colors is said to be the equitable chromatic threshold of G and is denoted by χ₌*(G). In this paper, we investigate the asymptotic behavior of these coloring parameters in the probability space G(n,p) of random graphs. We prove that if n^?1/5+? < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) = (1 + o(1))χ(G(n,p)) holds (where χ(G(n,p)) is the ordinary chromatic number of G(n,p)). We also show that there exists a constant C such that if C/n < p < 0.99, then almost surely χ(G(n,p)) ≤ χ₌(G(n,p)) ≤ (2 + o(1))χ(G(n,p)). Concerning the equitable chromatic threshold, we prove that if n^?(1??) < p < 0.99 for some 0 < ?, then almost surely χ(G(n,p)) ≤ χ₌* (G(n,p)) ≤ (2 + o(1))χ(G(n,p)) holds, and if < p < 0.99 for some 0 < ?, then almost surely we have χ(G(n,p)) ≤ χ₌*(G(n,p)) = O_?(χ(G(n,p))). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On Steiner 3-wise balanced designs of order 17

We determine all S(3, κ, 17)'s which either; (i) have a block of size at least 6; or (ii) have an automorphism group order divisible by 17, 5, or 3; or (iii) contain a semi-biplane; or (iv) come from an S(3, κ, 16) which is not an S(3, 4, 16). There is an S(3, κ, 17) with |G| = n if and only if n ϵ {2^a3^b: 0 ≤ a ≤ 7,0 ≤ b ≤ 1} ∪ {18, 60, 144, 288, 320, 1920, 5760, 16320}. We also search the S(3, κ, 17)'s listed in the appendix for subdesigns S(2, κ, 17) and generate 22 nonisomorphic S(3, κ, 18)'s by adding a new point to such a subdesign. © 1997 John Wiley & Sons, Inc.     

Isometric Isomorphisms Between Banach Algebras Related to a Certain Class of Clifford Topological Semigroups

In the present paper it is shown that if S₁ and S₂ are two Clifford topological semigroups satisfying certain conditions and T is an isometric isomorphism of LUC(S₁*) onto LUC(S₂*), then T maps S₁ topologically isomorphically onto S₂. Furthermore, T maps M ^l _n(S₁) (M(S₁), respectively) isometrically isomorphically onto M ^l _n(S₂) (M(S₂), respectively). Indeed, we have obtained a generalization of a well-known result of Ghahramani, Lau and Losert for locally compact groups to a more general setting of Clifford topological semigroups.     

Steiner systems andn −1-isomorphisms

In this work we introduce the concept of n ^–1-isomorphism between Steiner systems (this coincides with the concept of isomorphism whenever n=1).Precisely two Steiner systems S₁ and S₂ are said to be n^–1-isomorphic if there exist n partial systems S _i ⁽¹⁾ ,...,S _i ⁽ⁿ⁾ contained in Si, i.{1,2},such that S ₁ ^(k) and S ₂ ^(k) are isomorphic for each k{1,..., n}.The n^–1-isomorphisms are also used to study nets replacements, see Ostrom [8], and to study the transformation methods of designs and other incidence structures introduced in [9] and generalized in [1] and [10].Work done under the auspicies of G.N.S.A.G.A. supported by 40% grants of M.U.R.S.T.     

Alcune osservazioni sui sottogruppi abeliani del gruppoSp(n)·Sp(1)

Sunto Si studiano i sottogruppi abeliani diSp(n)·Sp(1). Viene data una caratterizzazione dei sottogruppi abeliani G diSp(n)·Sp(1) che sono immagini di sottogruppi abeliani del rivestimento universaleSp(n)·Sp(1). In relazione all'azione diSp(n)·Sp(1) su R⁴ⁿ ≡ Qⁿ si determinano i sottogruppi abeliani G per i quali Qⁿ si decompone nella somma diretta di di n sottospazi quaternionali1-dimensionali invarianti per G. Si caratterizzano i sottogruppi abeliani massimali tra quelli del tipo Z_p × … × Z_p (p numero primo). Entrata in Redazione il 21 Luglio 1976.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Recurrent approach to Blaschke’s problem

We have obtained a recurrence formula $I_{n+3} = \frac{4(n+3)}{\pi(n+4)}VI_{n+1}We have obtained a recurrence formula I_n+3 = \frac4(n+3)p(n+4)VI_n+1I_{n+3} = \frac{4(n+3)}{\pi(n+4)}VI_{n+1} for integro-geometric moments in the case of a circle with the area V, where I_n = ò\nolimits_{K ?G}sⁿd GI_n = \int \nolimits_{K \cap G}\sigma^{n}{\rm d} G, while in the case of a convex domain K with the perimeter S and area V the recurrence formula

In+3 = \frac8(n+3)V2(n+1)(n+4)p[\fracd In+1d V - \fracIn+1S \fracd Sd V ] I_{n+3} = \frac{8(n+3)V^2}{(n+1)(n+4)\pi}\Big[\frac{{\rm d} I_{n+1}}{{\rm d} V} - \frac{I_{n+1}}{S} \frac{{\rm d} S}{{\rm d} V} \Big]      15. The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)      S. B. Gashkov  I. S. Sergeev 《Moscow University Mathematics Bulletin》2009,64(4):139-143 Let n = (p − 1) · p k , where p is a prime number such that 2 is a primitive root modulo p, and 2 p−1 − 1 is not a multiple of p 2. For a standard basis of the field GF(2 n ), a multiplier of complexity O(log log p)n log n log log p n and an inverter of complexity O(log p log log p)n log n log log p n are constructed. In particular, in the case p = 3 the upper bound $ 5\frac{5} {8}n\log _3 n\log _2 \log _3 n + O(n\log n) $ 5\frac{5} {8}n\log _3 n\log _2 \log _3 n + O(n\log n)       16. Random and Deterministic Triangle Generation of Three-Dimensional Classical Groups III      Claude Marion 《代数通讯》2013,41(3):926-954 Let p1, p2, p3 be primes. This is the final paper in a series of three on the (p1, p2, p3)-generation of the finite projective special unitary and linear groups PSU 3(pn), PSL 3(pn), where we say a noncyclic group is (p1, p2, p3)-generated if it is a homomorphic image of the triangle group Tp1, p2, p3 . This article is concerned with the case where p1 = 2 and p2 ≠ p3. We determine for any primes p2 ≠ p3 the prime powers pn such that PSU 3(pn) (respectively, PSL 3(pn)) is a quotient of T = T2, p2, p3 . We also derive the limit of the probability that a randomly chosen homomorphism in Hom(T, PSU 3(pn)) (respectively, Hom(T, PSL 3(pn))) is surjective as pn tends to infinity.      17. On improved estimators of the generalized variance      Bimal Kumar Sinha 《Journal of multivariate analysis》1976,6(4):617-625 Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p Wp(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ Ik) with ξ(p × k) unknown. Denote the columns of X by X(1) ,…, X(k) and set ψ(0)(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ(i)(X, X) = min[ψ(i−1)(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X(1) X′(1) + + X(i) X′(i) |] and Ψ(i)(S, X) = min[ψ(0)(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X(1) X′(1) + + X(i) X′(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ(0)(S, X) is dominated by each of Ψ(i)(S, X), i = 1,…,k and for every i, ψ(i)(S, X) is better than ψ(i−1)(S, X). In particular, ψ(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X(1)X′(1)|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X(1)X′(1) + + X(k)X′(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.      18. Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions      Abdelbaki Boutabaa  Alain Escassut 《Rendiconti del Circolo Matematico di Palermo》2000,49(3):501-520 LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS n(b) of zeros of the polynomialx n−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf −1(S n(b))=g −1(S n(b)), thenf n=g n. For everyn≥14, we show thatS n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf −1(S n(b))=g −1(S n(b)), then eitherf n=g n, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.      19. A conjecture of recski in combinatorial set theory      Ki Hang Kim  Fred W Roush 《Journal of Combinatorial Theory, Series A》1979,26(1):87-89 A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ Si = n and |Si ∩ Si| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(np+1logn).      20. Approximation algorithms for Hamming clustering problems   总被引：1，自引：0，他引：1   Leszek G sieniec  Jesper Jansson  Andrzej Lingas 《Journal of Discrete Algorithms》2004,2(2):289 We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L1 metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2O(p/)kO(p/)n2-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in Full-size image time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

Random and Deterministic Triangle Generation of Three-Dimensional Classical Groups III

Let p₁, p₂, p₃ be primes. This is the final paper in a series of three on the (p₁, p₂, p₃)-generation of the finite projective special unitary and linear groups PSU ₃(pⁿ), PSL ₃(pⁿ), where we say a noncyclic group is (p₁, p₂, p₃)-generated if it is a homomorphic image of the triangle group T_{p1, p2, p3} . This article is concerned with the case where p₁ = 2 and p₂ ≠ p₃. We determine for any primes p₂ ≠ p₃ the prime powers pⁿ such that PSU ₃(pⁿ) (respectively, PSL ₃(pⁿ)) is a quotient of T = T_{2, p2, p3} . We also derive the limit of the probability that a randomly chosen homomorphism in Hom(T, PSU ₃(pⁿ)) (respectively, Hom(T, PSL ₃(pⁿ))) is surjective as pⁿ tends to infinity.     

On improved estimators of the generalized variance

Treated in this paper is the problem of estimating with squared error loss the generalized variance | Σ | from a Wishart random matrix S: p × p W_p(n, Σ) and an independent normal random matrix X: p × k N(ξ, Σ I_k) with ξ(p × k) unknown. Denote the columns of X by X₍₁₎ ,…, X_(k) and set ψ⁽⁰⁾(S, X) = {(n − p + 2)!/(n + 2)!} | S |, ψ⁽ⁱ⁾(X, X) = min[ψ⁽ⁱ⁻¹⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!} | S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |] and Ψ⁽ⁱ⁾(S, X) = min[ψ⁽⁰⁾(S, X), {(n − p + i + 2)!/(n + i + 2)!}| S + X₍₁₎ X′₍₁₎ + + X_(i) X′_(i) |], i = 1,…,k. Our result is that the minimax, best affine equivariant estimator ψ⁽⁰⁾(S, X) is dominated by each of Ψ⁽ⁱ⁾(S, X), i = 1,…,k and for every i, ψ⁽ⁱ⁾(S, X) is better than ψ⁽ⁱ⁻¹⁾(S, X). In particular, ψ^(k)(S, X) = min[{(n − p + 2)!/(n + 2)!} | S |, {(n − p + 2)!/(n + 2)!} | S + X₍₁₎X′₍₁₎|,…,| {(n − p + k + 2)!/(n + k + 2)!} | S + X₍₁₎X′₍₁₎ + + X_(k)X′_(k)|] dominates all other ψ's. It is obtained by considering a multivariate extension of Stein's result (Ann. Inst. Statist. Math. 16, 155–160 (1964)) on the estimation of the normal variance.     

Propertyf −1(S) =g −1(S) for entire and meromorphicP-adic functions

LetW be an algebraically closed filed of characteristic zero, letK be an algebraically closed field of characteristic zero, complete for an ultrametric absolute value, and letA(K) (resp. ℳ(K)) be the set of entire (resp. meromorphic) functions inK. For everyn≥7, we show that the setS _n(b) of zeros of the polynomialx ⁿ−b (b≠0) is such that, iff, g ∈W[x] or iff, g ∈A(K), satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), thenf ⁿ=g ⁿ. For everyn≥14, we show thatS _n(b) is such that iff, g ∈W({tx}) or iff, g ∈ ℳ(K) satisfyf ⁻¹(S _n(b))=g ⁻¹(S _n(b)), then eitherf ⁿ=g ⁿ, orfg is a constant. Analogous properties are true for complex entire and meromorphic functions withn≥8 andn≥15, respectively. For everyn≥9, we show that the setY _n(c) of zeros of the polynomial , (withc≠0 and 1) is an ursim ofn points forW[x], and forA(K). For everyn≥16, we show thatY _n(c) is an ursim ofn points forW(x), and for ℳ(K). We follow a method based on thep-adic Nevanlinna Theory and use certain improvement of a lemma obtained by Frank and Reinders.     

A conjecture of recski in combinatorial set theory

A p-cover of $\text{n = {1, 2,…,}\text{n}\text{}}$ is a family of subsets $\text{S}{}_{\mathrm{i}}\text{≠ ?}$ such that ∪ S_i = n and |S_i ∩ S_i| ? p for i ≠ j. We prove that for fixed p, the number of p-cover of n is O(n^p+1logn).     

Approximation algorithms for Hamming clustering problems

We study Hamming versions of two classical clustering problems. The Hamming radius p-clustering problem (HRC) for a set S of k binary strings, each of length n, is to find p binary strings of length n that minimize the maximum Hamming distance between a string in S and the closest of the p strings; this minimum value is termed the p-radius of S and is denoted by . The related Hamming diameter p-clustering problem (HDC) is to split S into p groups so that the maximum of the Hamming group diameters is minimized; this latter value is called the p-diameter of S.We provide an integer programming formulation of HRC which yields exact solutions in polynomial time whenever k is constant. We also observe that HDC admits straightforward polynomial-time solutions when k=O(logn) and p=O(1), or when p=2. Next, by reduction from the corresponding geometric p-clustering problems in the plane under the L₁ metric, we show that neither HRC nor HDC can be approximated within any constant factor smaller than two unless P=NP. We also prove that for any >0 it is NP-hard to split S into at most pk^1/7− clusters whose Hamming diameter does not exceed the p-diameter, and that solving HDC exactly is an NP-complete problem already for p=3. Furthermore, we note that by adapting Gonzalez' farthest-point clustering algorithm [T. Gonzalez, Theoret. Comput. Sci. 38 (1985) 293–306], HRC and HDC can be approximated within a factor of two in time O(pkn). Next, we describe a 2^O(p/)k^O(p/)n²-time (1+)-approximation algorithm for HRC. In particular, it runs in polynomial time when p=O(1) and =O(log(k+n)). Finally, we show how to find in

Full-size image

time a set L of O(plogk) strings of length n such that for each string in S there is at least one string in L within distance (1+), for any constant 0<<1.