Resolvability and the upper dimension of graphs

For an ordered set W = {w₁, w₂,…, w_k} of vertices and a vertex v in a connected graph G, the (metric) representation of v with respect to W is the k-vector r(v | W) = (d(v, w₁), d(v, w₂),…, d(v, w_k)), where d(x, y) represents the distance between the vertices x and y. The set W is a resolving set for G if distinct vertices of G have distinct representations. A new sharp lower bound for the dimension of a graph G in terms of its maximum degree is presented.

A resolving set of minimum cardinality is a basis for G and the number of vertices in a basis is its (metric) dimension dim(G). A resolving set S of G is a minimal resolving set if no proper subset of S is a resolving set. The maximum cardinality of a minimal resolving set is the upper dimension dim⁺(G). The resolving number res(G) of a connected graph G is the minimum k such that every k-set W of vertices of G is also a resolving set of G. Then 1 ≤ dim(G) ≤ dim⁺(G) ≤ res(G) ≤ n − 1 for every nontrivial connected graph G of order n. It is shown that dim⁺(G) = res(G) = n − 1 if and only if G = K_n, while dim⁺(G) = res(G) = 2 if and only if G is a path of order at least 4 or an odd cycle.

The resolving numbers and upper dimensions of some well-known graphs are determined. It is shown that for every pair a, b of integers with 2 ≤ a ≤ b, there exists a connected graph G with dim(G) = dim⁺(G) = a and res(G) = b. Also, for every positive integer N, there exists a connected graph G with res(G) − dim⁺(G) ≥ N and dim⁺(G) − dim(G) ≥ N.     

Periodic solutions of a class of nonlinear difference equations via critical point method

In this paper, we obtain some new sufficient conditions for the existence of nontrivial m-periodic solutions of the following nonlinear difference equation

by using the critical point method, where f: Z × R → R is continuous in the second variable, m ≥ 2 is a given positive integer, p_n+m = p_n for any n  Z and f(t + m, z) = f(t, z) for any (t, z)  Z × R, (−1)^δ = −1 and δ > 0.     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

Fast adaptive PNN-based thresholding algorithms

Thresholding is a fundamental operation in image processing. Based on the pairwise nearest neighbor technique and the variance criterion, this theme presents two fast adaptive thresholding algorithms. The proposed first algorithm takes O((m−k)mτ) time where k denotes the number of thresholds specified by the user; m denotes the size of the compact image histogram, and the parameter τ has the constraint 1τm. On a set of different real images, experimental results reveal that the proposed first algorithm is faster than the previous three algorithms considerably while having a good feature-preserving capability. The previous three mentioned algorithms need O(m^k) time. Given a specific peak-signal-to-noise ratio (PSNR), we further present the second thresholding algorithm to determine the number of thresholds as few as possible in order to obtain a thresholded image satisfying the given PSNR. The proposed second algorithm takes O((m−k)mτ+γN) time where N and γ denote the image size and the fewest number of thresholds required, respectively. Some experiments are carried out to demonstrate the thresholded images that are encouraging. Since the time complexities required in our proposed two thresholding algorithms are polynomial, they could meet the real-time demand in image preprocessing.     

Complexities of special matrix multiplication problems

This paper develops optimal algorithms to multiply an n × n symmetric tridiagonal matrix by: (i) an arbitrary n × m matrix using 2nm − m multiplications; (ii) a symmetric tridiagonal matrix using 6n − 7 multiplications; and (iii) a tridiagonal matrix using 7n −8 multiplications. Efficient algorithms are also developed to multiply a tridiagonal matrix by an arbitrary matrix, and to multiply two tridiagonal matrices.     

On-line parallel heuristics, processor scheduling and robot searching under the competitive framework

In this paper we investigate parallel searches on m concurrent rays for a point target t located at some unknown distance along one of the rays. A group of p agents or robots moving at unit speed searches for t. The search succeeds when an agent reaches the point t. Given a strategy S the competitive ratio is the ratio of the time needed by the agents to find t using S and the time needed if the location of t had been known in advance. We provide a strategy with competitive ratio of 1+2(m/p−1)(m/(m−p))^m/p and prove that this is optimal. This problem has applications in multiple heuristic searches in AI as well as robot motion planning. The case p = 1 is known in the literature as the cow path problem.     

Parallel clustering algorithms

Clustering techniques play an important role in exploratory pattern analysis, unsupervised learning and image segmentation applications. Many clustering algorithms, both partitional clustering and hierarchical clustering, require intensive computation, even for a modest number of patterns. This paper presents two parallel clustering algorithms. For a clustering problem with N = 2ⁿ patterns and M = 2^m features, the time complexity of the traditional partitional clustering algorithm on a single processor computer is O(MNK), where K is the number of clusters. The proposed algorithm on anSIMD computer with MN processors has a time complexity O(K(n + m)). The time complexity of the proposed single-link hierarchical clustering algorithm is reduced from O(MN²) of the uniprocessor algorithm to O(nN) with MN processors.     

Fast evaluation of radial basis functions: I

This paper describes some new techniques for the rapid evaluation and fitting of radial basic functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = Σ_j=1^N d_jφ(x−x_j), where φ(u) = |u|²log|u|, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision ε, can be cut to O(1+|log ε|) operations. In particular, if A is the interpolation matrix, a_i,j = φ(x_i−x_j, the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N²) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.     

Electrocatalytic oxidation of methanol and other short chain aliphatic alcohols on glassy carbon electrodes modified with conductive films derived from Ni-(N,N′-bis(2,5-dihydroxybenzylidene)-1,2-diaminobenzene)

Complexes of nickel(II) with the ligand N,N′-bis(2,5-dihydroxybenzylidene)-1,2-diaminobenzene (Ni^II-DHS) can be electropolymerized onto glassy carbon surfaces in alkaline solution to give electroactive films strongly adhered on the electrode surface. In alkaline solution, these poly-[Ni^II-DHS]/GC films present the typical voltammetric response of a surface-immobilized redox couple, as can be anticipated for the Ni²⁺/Ni³⁺ transitions into the film. In addition, the films exhibit a potent and persistent electrocatalytic activity towards the oxidation of methanol. The electrocatalytic currents are, at least, 80 times higher than those obtained for the oxidation of methanol at electrodes modified with nickel hydroxide films in alkaline solutions. In addition, the current is proportional to the concentration of methanol from 0.050 to 0.30 μM. The detection limit and the sensitivity were found to be 26 ± 2 nM and 7.4 × 10⁻² ± 6 × 10⁻³ A cm² mol⁻¹ M⁻¹, respectively. Electrodes modified with poly-[Ni^II-DHS]/GC films show a moderate electrocatalytic activity towards the oxidation of other aliphatic short chain alcohols, such as: ethanol, 1-propanol, 2-propanol and n-butanol. In all cases the catalytic currents present linear dependences with the concentration of alcohol in alkaline solution. The analytical properties of these potential alcohol sensors have also been studied.     

A simple approximation for the Erlang loss function

In this paper we present a simple non-iterative computational procedure for approximating the Erlang loss function B(N, ). It is applicable to the practical range 10⁻⁵<B(N, )<10⁻¹ and gives results that are within 10% of the exact values. The formula can be computed on a pocket calculator in constant time and could be used to approximately compute B(N, ) for systems of practically any size.     

Least adaptive optimal search with unreliable tests

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let q_e(m) be the smallest integer q satisfying Berlekamp’s bound . Then at least q_e(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly q_e(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly q_e(m) questions—or equivalently, e-error correcting codes with 2^m codewords of length q_e(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of q_e(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, q_e(m)−1 questions do not suffice to find the unknown number, and q_e(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.     

Simulation and fabrication of piezoresistive membrane type MEMS strain sensors

Two piezoresistive (n-polysilicon) strain sensors on a thin Si₃N₄/SiO₂ membrane with improved sensitivity were successfully fabricated by using MEMS technology. The primary difference between the two designs was the number of strips of the polysilicon patterns. For each design, a doped n-polysilicon sensing element was patterned over a thin 3 μm Si₃N₄/SiO₂ membrane. A 1000×1000 μm² window in the silicon wafer was etched to free the thin membrane from the silicon wafer. The intent of this design was to fabricate a flexible MEMS strain sensor similar in function to a commercial metal foil strain gage. A finite element model of this geometry indicates that strains in the membrane will be higher than strains in the surrounding silicon. The values of nominal resistance of the single strip sensor and the multi-strip sensor were 4.6 and 8.6 kΩ, respectively. To evaluate thermal stability and sensing characteristics, the temperature coefficient of resistance [TCR=(ΔR/R₀)/ΔT] and the gage factor [GF=(ΔR/R₀)/] for each design were evaluated. The sensors were heated on a hot plate to measure the TCR. The sensors were embedded in a vinyl ester epoxy plate to determine the sensor sensitivity. The TCR was 7.5×10⁻⁴ and 9.5×10⁻⁴/°C for the single strip and the multi-strip pattern sensors. The gage factor was as high as 15 (bending) and 13 (tension) for the single strip sensor, and 4 (bending) and 21 (tension) for the multi-strip sensor. The sensitivity of these MEMS sensors is much higher than the sensitivity of commercial metal foil strain gages and strain gage alloys.     

Moments of conjugacy classes of binary words

For each nonempty binary word w=c₁c₂c_q, where c_i{0,1}, the nonnegative integer ∑_i=1^q (q+1−i)c_i is called the moment of w and is denoted by M(w). Let [w] denote the conjugacy class of w. Define M([w])={M(u): u[w]}, N(w)={M(u)−M(w): u[w]} and δ(w)=max{M(u)−M(v): u,v[w]}. Using these objects, we obtain equivalent conditions for a binary word to be an -word (respectively, a power of an -word). For instance, we prove that the following statements are equivalent for any binary word w with |w|2: (a) w is an -word, (b) δ(w)=|w|−1, (c) w is a cyclic balanced primitive word, (d) M([w]) is a set of |w| consecutive positive integers, (e) N(w) is a set of |w| consecutive integers and 0N(w), (f) w is primitive and [w]St.     

Parallel nested dissection

Nested dissection is a very popular direct method for solving sparse linear systems that arise from finite difference and finite element methods. Worley and Schreiber [16] give a fine grain algorithm for a square array of processors. Their algorithm uses O(N²) processors, each with O(N) memory, to factor an N² by N² sparse matrix whose graphs is an N × N mesh. The efficiency of their method is between 1/46 and 1/12. George et al. [6] [8] give a medium grain algorithm for hypercube architecture, while George et al. [7] give an algorithm for shared memory machines. These papers present a column oriented approach which can exploit O(N) parallelism and yield efficiencies up to 50%. Lucas [11] also gives a column oriented scheme which achieves up to 75% efficiency and O(N) parallelism. In this paper, we present a medium to fine grain algorithm for a P × P array of processors with local memory. This algorithm can exploit up to O(N²) parallelism. The efficiency of the fine grain version is comparable to [16] while as a medium grain algorithm achieves about 49% efficiency. The strength of the method is due to three factors: its ability to pipeline much of the computation, overlapping computation and communication, and the use of level 3 BLAS like primitives. In addition to its high efficiency its memory requirement is optimal, only O(N² log N/P²) words memory is needed per processor.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Fluorescence quenching of benzo[k]fluoranthene in poly(vinyl alcohol) film: a possible optical sensor for nitro aromatic compounds

Benzo[k]fluoranthene (BkF) is a condensed multi-ring compounds with high fluorescence quantum yield and Stokes’ shift. Nitro aromatic compounds (NACs) are known to be good electron acceptors and quenchers. The fluorescence quenching of benzo[k]fluoranthene in poly(vinyl alcohol) film by different NACs, e.g. nitrobenzene, m-dinitrobenzene, o-nitrotoluene, m-nitrotoluene, p-nitrobromobenzene, o-nitroaniline, p-nitrophenol, etc. has been studied. The BkF film shows a strong quenching in the NACs concentration range from 1×10⁻⁴ to 1×10⁻³ M. The Stern–Volmer plots for NACs are found to be non-linear, but regular in this concentration range, which can be used for estimation of these compounds. The typical response time of the sensing film is found to be 2–10 s. The sensor film also shows minimal interference from different organic molecules and has good reversibility and reproducibility. The sensor gives a sensitivity of 1×10⁻⁵ M for p-nitrophenol.     

Metallic thin-film thermocouple for thermoelectric microgenerators

A new metallic thin-film thermocouple orientated towards thermoelectric microgenerators has been developed. It consists of a 3 μm thick NiCr/SiO₂/Sb multilayer structure sputter deposited onto a thermally oxidized silicon substrate. A relative Seebeck coefficient of _ab = 76 μV K⁻¹ and an optimal figure of merit of z_ab = 0.08 × 10⁻³ K⁻¹ have been measured for this material combination. Both parameters are very close to the theoretical values.     

Confluent general-factorial difference and derivative operators and polynomial-exponential interpolation

A previous application of the Newton divided difference series of the displacement function E^z = (1 + Δ)^z = e ^Dz, where the operators Δ and D are the variables, to purely exponential interpolation employing general-factorial differences and derivatives, {Pi;^m_i=0 (Δ - S_i)}f(0) and {Pi;^m_i=0 (D - t_i)}f(0), in which the s_i's and t_i's are distinct[1], is here extended to mixed polynomial-exponential interpolation where the s_i's and t_i's are no longer distinct.