The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

A graph is an interval graph if and only if each vertex in the graph can be associated with an interval on the real line such that any two vertices are adjacent in the graph exactly when the corresponding intervals have a nonempty intersection. A number of interesting applications for interval graphs have been found in the literature. In order to find structural features common to structural data which can be represented by intervals, this paper proposes new interval graph structured patterns, called linear interval graph patterns, and a polynomial time algorithm for finding a minimally generalized linear interval graph pattern explaining a given finite set of interval graphs.

A space-efficient approximation algorithm for the grammar-based compression problem, which requests for a given string to find a smallest context-free grammar deriving the string, is presented. For the input length n and an optimum CFG size g, the algorithm consumes only O(g log g) space and O(n log*n) time to achieve O((log*n)log n) approximation ratio to the optimum compression, where log*n is the maximum number of logarithms satisfying log log log n > 1. This ratio is thus regarded to almost O(log n), which is the currently best approximation ratio. While g depends on the string, it is known that g=Ω(log n) and for strings from k-letter alphabet [12].

In this letter, we propose a novel singular value decomposition zero-forcing beamforming (SVD-ZFBF) relaying scheme in the multiuser downlink MIMO broadcasting channel with fixed relays. Based on the processing scheme, we apply SUS [5] to select users at the relay station (RS) and develop a joint power allocation strategy at the base station (BS) and RS. By increasing the power at RS or selecting active users to obtain more multiuser diversity, SVD-ZFBF can approach an upper bound and outperform SVD-ZFDPC [1] with much lower complexity. Moreover, we show that the noise power ratio of RS to users significantly impacts the performance.

This work elucidates the evolution of three generations of the laboratory information system in the National Taiwan University Hospital, which were respectively implemented in an IBM Series/1 minicomputer, a client/server and a plug-and-play HL7 interface engine environment respectively. The experience of using the HL7 healthcare information exchange in the hospital information system, laboratory information system, and automatic medical instruments over the past two decades are illustrated and discussed. The latest design challenge in developing intelligent laboratory information services is to organize effectively distributed and heterogeneous medical instruments through the message gateways. Such experiences had spread to some governmental information systems for different purposes in Taiwan; besides, the healthcare information exchange standard, software reuse mechanism, and application service provider adopted in developing the plug-and-play laboratory information system are also illustrated.

Particle Image Velocimetry (PIV) is a widely used tool for the measurement of the different kinematic properties of the fluid flow. In this measurement technique, a pulsed laser light sheet is used to illuminate a flow field seeded with tracer particles and at each instance of illumination, the positions of the particles are recorded on digital CCD cameras. The resulting two camera frames can then be processed by various techniques to obtain the velocity vectors. One such techniques involve the tracking of the individual particles so as to identify the displacement of the every particles present in the flow field. The displacement of individual particles thus determined gives the velocity information if divided by known time interval. The accuracy as well as efficiency of such measurement systems depend upon the reliability of the algorithms to track those particles. In the present work, a cellular neural network based algorithm has been proposed. Performance test has been carried out using the standard flow images. It performs well in comparison to the existing algorithms in terms of reliability, accuracy and processing time.

Eigen-beamforming (EB) transmission for multiple-input multiple-output (MIMO) systems is an effective means to maximize the receiver signal-to-noise ratio (SNR) in a noise-limited environment, but suffers a performance degradation when strong interference signals exist. In this letter, we propose an interference cancellation method for EB signals by constructing a new receive beamforming vector which jointly utilizes the EB matrix and minimum mean-square error (MMSE) spatial demultiplexing. The proposed method is shown to outperform the conventional EB receiver in the entire cell range, with a significant increase in the effective signal-to-interference plus noise ratio (SINR) near the cell boundary.

An elementary formal system, EFS for short, is a kind of logic program over strings, and regarded as a set of rules to generate a language. For an EFS Γ, the language L(Γ) denotes the set of all strings generated by Γ. We consider a new form of EFS, called a restricted two-clause EFS, and denote by rEFS the set of all restricted two-clause EFSs. Then we study the learnability of rEFS in the exact learning model. The class rEFS contains the class of regular patterns, which is extensively studied in Learning Theory. Let Γ* be a target EFS in rEFS of learning. In the exact learning model, an oracle for superset queries answers "yes" for an input EFS Γ in rEFS if L(Γ) is a superset of L(Γ*), and outputs a string in L(Γ*)-L(Γ), otherwise. An oracle for membership queries answers "yes" for an input string w if w is included in L(Γ*), and answers "no", otherwise. We show that any EFS in rEFS is exactly identifiable in polynomial time using membership and superset queries. Moreover, for other types of queries, we show that there exists no polynomial time learning algorithm for rEFS by using the queries. This result indicates the hardness of learning the class rEFS in the exact learning model, in general.

The authors present R2Power, an effective approach to the realizable reduction of RC networks with independent current sources. The proposed approach is based on the entrywise perturbation theory for diagonally dominant M-matrices. The accuracy of the node voltages of the reduced network, as compared to those of the original network, is maintained on the order of the entrywise perturbation performed during reduction. R2Power can be used to reduce the size of RC networks used to model the power networks of SoCs, for efficient IR-drop analysis. Experiments showed that R2Power reduced the size of industrial examples by more than 95%, with maximum relative node voltage errors of less than 0.012%.

In this paper, an efficient partial incremental redundancy (P-IR) scheme is proposed for an H-ARQ using block type low density parity check (B-LDPC) codes. The performance of the proposed P-IR scheme is evaluated in an HSDPA system using IEEE 802.16e B-LDPC codes. Simulation results show that the proposed H-ARQ using IEEE 802.16e B-LDPC codes outperforms the H-ARQ using 3GPP turbo codes.

Construction of quaternion design for Space-Time-Polarization Block Codes (STPBCs) is a hot but difficult topic. This letter introduces a novel way to construct high dimensional quaternion designs based on any existing low dimensional quaternion orthogonal designs(QODs) for STPBC, while preserving the merits of the original QODs such as full diversity and simple decoding. Furthermore, it also provides a specific schema to reach full diversity and maximized code gain by signal constellation rotation on the polarization plane.

In the proposed scheme, every sensor establishes communications keys with its neighbors after deployment. They are selectively employed for intra-cluster communications, and the employed keys are determined by local topology of clusters. Thus, our scheme periodically changes the local topology of clusters so as to renew the intra-cluster communication keys. Besides, new Cluster Heads (CHs) easily share a key with the Base Station (BS) by informing the BS of their member information without sending key materials. Simulation results prove that our approach has strong resiliency against the increase of compromised sensors. It also achieves a performance gain in terms of energy.

Although each application has its own quality of service (QoS) requirements, the resource allocation for multiclass services has not been studied adequately in multiuser orthogonal frequency division multiplexing (OFDM) systems. In this paper, a total transmit power minimization problem for downlink transmission is examined while satisfying multiclass services consisting of different data rates and target bit-error rates (BER). Lagrangian relaxation is used to find an optimal subcarrier allocation criterion in the context of subcarrier time-sharing by all users. We suggest an iterative algorithm using this criterion to find the upper and lower bounds of optimal power consumption. We also propose a prioritized subcarrier allocation (PSA) algorithm that provides low computation cost and performance very close to that of the iterative algorithm. The PSA algorithm employs subcarrier selection order (SSO) in order to decide which user takes its best subcarrier first over other users. The SSO is determined by the data rates, channel gain, and target BER of each user. The proposed algorithms are simulated in various QoS parameters and the fading channel model. Furthermore, resource allocation is performed not only subcarrier by subcarrier but also frequency block by frequency block (comprises several subcarriers). These extensive simulation environments provide a more complete assessment of the proposed algorithms. Simulation results show that the proposed algorithms significantly outperform existing algorithms in terms of total transmit power consumption.

Silicon photonic devices based on silicon photonic wire waveguides are especially attractive devices, since they can be ultra-compact and low-power consumption. In this paper, we demonstrated various devices fabricated on silicon photonic wire waveguides. They included optical directional couplers, reconfigurable optical add/drop multiplexers, 12, 14, 18 and 44 optical switches, ring resonators. The characteristics of these devices show that silicon photonic wire waveguides offer promising platforms in constructing compact and power-saving photonic devices and systems.

We propose a gap-less optical interconnection between BGA package and board for practical on-board, chip-to-chip optical interconnection. The optical interconnect consists of polymer optical waveguides, an integral mirror on the PWB (printed wiring board), an optical via hole through package, and a connection structure and method requiring no alignment process. Optical waveguide, mirror, waveguide extensions and alignment studs were fabricated on the PWB as horizontal optical interconnect. Coaxial structured optical vias with core and cladding were formed through the package and with precise holes for alignment. Two packages were attached onto the PWB using standard BGA technology utilizing passive optical alignment. The optical characteristics and 10 Gbit/s open-eye diagram were measured. A completely gap-less three dimensional optical interconnect between package-PWB-package was demonstrated.

This paper introduces a new timetabling problem on universities, called interview timetabling. In this problem, some constant number, say three, of referees are assigned to each of 2n graduate students. Our task is to construct a presentation timetable of these 2n students using n timeslots and two rooms, so that two students evaluated by the same referee must be assigned to different timeslots. The optimization goal is to minimize the total number of movements of all referees between two rooms. This problem comes from the real world in the interview timetabling in Kyoto University. We propose two restricted models of this problem, and investigate their time complexities.

Jitter is the variation of latencies, when real-time Intellectual Properties (IPs) are accessing data from the data storages. It is a critical factor for such IPs from the Quality-of-Service (QoS) perspective. Jitter of a real-time IP can be measured by how frequently it experiences the underflows and overflows from its data queue in read mode and write mode, respectively. Such failures critically depend on the bus arbitration scheme which determines the bus acquisition order of IPs. The proposed idea allows IPs to inform the bus arbiter of the status of their data buffers when they assert bus requests. Such information helps the bus arbiter to determine the bus acquisition order while greatly reducing the jitter. The experimental results show that our method effectively eliminates the overflows and underflows of real-time IPs by dynamically preempting the jitter-critical bus requests.

In this paper, a perceptually adaptive watermarking scheme for color images is proposed in order to achieve robustness and transparency. A new just noticeable distortion (JND) estimator for color images is first designed in the wavelet domain. The key issue of the JND model is to effectively integrate visual masking effects. The estimator is an extension to the perceptual model that is used in image coding for grayscale images. Except for the visual masking effects given coefficient by coefficient by taking into account the luminance content and the texture of grayscale images, the crossed masking effect given by the interaction between luminance and chrominance components and the effect given by the variance within the local region of the target coefficient are investigated such that the visibility threshold for the human visual system (HVS) can be evaluated. In a locally adaptive fashion based on the wavelet decomposition, the estimator applies to all subbands of luminance and chrominance components of color images and is used to measure the visibility of wavelet quantization errors. The subband JND profiles are then incorporated into the proposed color image watermarking scheme. Performance in terms of robustness and transparency of the watermarking scheme is obtained by means of the proposed approach to embed the maximum strength watermark while maintaining the perceptually lossless quality of the watermarked color image. Simulation results show that the proposed scheme with inserting watermarks into luminance and chrominance components is more robust than the existing scheme while retaining the watermark transparency.

In this paper we present hybrid positioning schemes that combine time of arrival (TOA) and angle of arrival (AOA) measurements from only two base stations (BSs) to locate the mobile station (MS) in non-line-of-sight (NLOS) environments. The proposed methods utilize two TOA circles and two AOA lines to find all the possible intersections to locate the MS without requiring a priori information about the NLOS error. The commonly known Taylor series algorithm (TSA) and the hybrid lines of position algorithm (HLOP) have convergence problems, and the relative positioning between the MS and the BSs greatly affects the location accuracy. The resulting geometry creates a situation where small measurement errors can lead to significant errors in the estimated MS location. Simulation results show that the proposed methods always perform better than TSA and HLOP for different levels of NLOS errors, particularly when the MS/BSs have an undesirable geometric layout.

Trust negotiation is an authorizing technique based on digital credentials, in which both a user and a server gradually establish trust in each other by repeatedly exchanging their credentials. A trust negotiation strategy is a function that answers a set of credentials to disclose to the other party, depending on policies and the set of already disclosed credentials. The disclosure tree strategy (DTS), proposed by Yu et al., is one of the strategies that satisfies preferable properties. DTS in a simple implementation requires exponential time and space; however, neither an efficient algorithm nor the lower-bound of its complexity was known. In this paper, we investigate the computational complexity of DTS. We formulate subproblems of DTS as problems on derivation trees of a context-free grammar (CFG), and analyze the computational complexity of the subproblems using the concepts of CFGs. As a result, we show that two subproblems EVL and MSET of DTS are NP-complete and NP-hard, respectively, while both are solvable in polynomial time if we modify EVL not to require non-redundancy and MSET not to answer any subset useless for leading the negotiation to success.