We consider an edge-weighted graph G with a designated vertex v0 such that weights of edges incident to v0 may increase or decrease. We show that, with an O(mn+n2log n) time preprocessing, a minimum cut of the current G can be computed in O(log n) time per update of weight of any edge {v0,u}.

Thanks to recent improvements in road heating technology, traffic problems due to icy roads are decreasing. However, there has always been concern about the high operational and maintenance cost associated with road heating. One way to reduce the cost is to reduce the time when power is applied for preheating because it is often applied even when a road is not likely to be icy. The authors believe that, if it is possible to forecast accurately whether a road will become icy, unnecessary preheating can be greatly reduced. This paper presents an algorithm for forecasting physical road conditions. The algorithm divides the weather conditions that people perceive daily into 11 patterns. The comparison between the changes in road conditions as determined by our method and known changes in road conditions has shown a 12% increase over previous methods in forecasting accuracy.

Assume that each vertex of a graph G is assigned a constant number q of nonnegative integer weights, and that q pairs of nonnegative integers li and ui, 1 ≤ i ≤ q, are given. One wishes to partition G into connected components by deleting edges from G so that the total i-th weights of all vertices in each component is at least li and at most ui for each index i, 1 ≤ i ≤ q. The problem of finding such a "uniform" partition is NP-hard for series-parallel graphs, and is strongly NP-hard for general graphs even for q = 1. In this paper we show that the problem and many variants can be solved in pseudo-polynomial time for series-parallel graphs and partial k-trees, that is, graphs with bounded tree-width.

An improved methodology, based on the genetic algorithm, is developed to design thermal-via structures and circuit parameters of advanced InGaP and InGaAs collector-up heterojunction bipolar transistors (C-up HBTs), which are promising miniature high-power amplifiers (HPAs) in cellular communication systems. Excellent simulated and measured results demonstrate the usefulness of this technique.

We present theoretical foundations about error estimations of the global Krylov subspace techniques for multiple-inputs multiple-outputs (MIMO) Interconnect reductions. Analytical relationships between Lyapunov functions of the original interconnect network and those of the reduced system generated by the global Arnoldi algorithm will be developed. Under this framework, a new moment matching reduced network is proposed. Also, we will show that the reduced system can be expressed as the original network with some additive perturbations.

This paper presents a fast transient simulation method for power distribution networks (PDNs) of the PCB/Package. Because these PDNs are modeled as large-scale linear circuits consisting of a large number of RLC elements, it takes large costs to solve by conventional circuit simulators, such as SPICE. Our simulation method is based on the leapfrog algorithm, and can solve RLC circuits of PDNs faster than SPICE. Actual PDNs have frequency-dependent dispersions such as the skin-effect of conductors and the dielectric loss. To model these dispersions, more number of RLC elements are required, and circuit structures of these dispersion models are hard to solve by using the leapfrog algorithm. This paper shows that the circuit structures of dispersion models can be converted to suitable structures for the leapfrog algorithm. Further, in order to reduce the simulation time, our proposed method exploits parallel computation techniques. Numerical results show that our proposed method using single processing element (PE) enables a speedup of 20-100 times and 10 times compared to HSPICE and INDUCTWISE with the same level of accuracy, respectively. In a large-scale example with frequency-dependent dispersions, our method achieves over 94% parallel efficiency with 5PEs.

Let G be any graph with property P (for example, general graph, directed graph, etc.) and S be nonnegative and non-decreasing integer sequence(s). The prescribed degree sequence problem is a problem to determine whether there is a graph G having S as the prescribed sequence(s) of degrees or outdegrees of the vertices. From 1950's, P has attracted wide attentions, and its many extensions have been considered. Let P be the property satisfying the following (1) and (2):(1) G is a directed graph with two disjoint vertex sets A and B. (2) There are r11 (r22, respectively) directed edges between every pair of vertices in A(B), and r12 directed edges between every pair of vertex in A and vertex in B. Then G is called an (r11, r12, r22)-tournament ("tournament", for short). The problem is called the score sequence pair problem of a "tournament" (realizable, for short). S is called a score sequence pair of a "tournament" if the answer of the problem is "yes." In this paper, we propose the characterizations of a score sequence pair of a "tournament" and an algorithm for determining in linear time whether a pair of two integer sequences is realizable or not.

When Simulated Annealing (SA) is applied to continuous optimization problems, the design of the neighborhood used in SA becomes important. Many experiments are necessary to determine an appropriate neighborhood range in each problem, because the neighborhood range corresponds to distance in Euclidean space and is decided arbitrarily. We propose Multi-point Simulated Annealing with Adaptive Neighborhood (MSA/AN) for continuous optimization problems, which determine the appropriate neighborhood range automatically. The proposed method provides a neighborhood range from the distance and the design variables of two search points, and generates candidate solutions using a probability distribution based on this distance in the neighborhood, and selects the next solutions from them based on the energy. In addition, a new acceptance judgment is proposed for multi-point SA based on the Metropolis criterion. The proposed method shows good performance in solving typical test problems.

We consider a problem for constructing a minimum cost r-edge-connected multigraph in which degree d(v) of each vertex v ∈ V is specified. In this paper, we propose a 3-approximation algorithm for this problem under the assumption that edge cost is metric, r(u,v) ∈ {1,2} for each u,v ∈ V, and d(v) ≥ 2 for each v ∈ V. This problem is a generalization of metric TSP. We also propose an approximation algorithm for the digraph version of the problem.

For execution of computation-intensive applications, one of the most important paradigms is to divide the application into a large number of small independent tasks and execute them on heterogeneous parallel computing environments (abbreviated by HPCEs). In this paper, we aim to execute independent tasks efficiently on HPCEs. We consider the problem to find a schedule that maximizes the throughput of task execution for a huge number of independent tasks. First, for HPCEs where the network forms a directed acyclic graph, we show that we can find, in polynomial time, a schedule that attains the optimal throughput. Secondly, for arbitrary HPCEs, we propose an (+ε)-approximation algorithm for any constant ε(ε>0). In addition, we also show that the framework of our approximation algorithm can be applied to other collective communications such as the gather operation.

In this paper, a recognition algorithm for the class of tree languages generated by linear, monadic context-free tree grammars (LM-CFTGs) is proposed. LM-CFTGs define an important class of tree languages because LM-CFTGs are weakly equivalent to tree adjoining grammars (TAGs). The algorithm uses the CKY algorithm as a subprogram and recognizes whether an input tree can be derived from a given LM-CFTG in O(n4) time, where n is the number of nodes of the input tree.

Decoding performance of LDPC (Low-Density Parity-Check) codes is highly dependent on the degree distributions of the Tanner graphs which define the LDPC codes. We compare two LDPC code ensembles, one has a uniform degree distribution and the other a non-uniform one over a BEC (Binary Erasure Channel) and a BSC (Binary Symmetric Channel) thorough DE (Density Evolution). We then derive sufficient conditions on the erasure probability of a BEC and the error probability of a BSC, under which the LDPC code ensembles with uniform degree distributions outperform those with non-uniform degree distributions.

An iterative reconstruction algorithm of accelerating the estimation of the complex relative permittivity of a cylindrical dielectric object based on the multigrid optimization method (MGOM) is presented. A cost functional is defined by the norm of a difference between the scattered electric fields measured and calculated for an estimated contrast function, which is expressed as a function of the complex relative permittivity of the object. Then the electromagnetic inverse scattering problem can be treated as an optimization problem where the contrast function is determined by minimizing the cost functional. We apply the conjugate gradient method (CGM) and the frequency-hopping technique (FHT) to the minimization of the cost functional, and also employ the multigrid method (MGM) with a V-cycle to accelerate the rate of convergence for getting the reconstructed profile. The reconstruction scheme is called the multigrid optimization method. Computer simulations are performed for lossy and inhomogeneous dielectric circular cylinders by using single-frequency or multifrequency scattering data. The numerical results demonstrate that the rate of convergence of the proposed metod is much faster than that of the conventional CGM for both noise-free and noisy cases.

This paper proposes an iterative maximum a posteriori probability (MAP) receiver for multiple-input-multiple-output (MIMO) and orthogonal frequency-division multiplexing (OFDM) mobile communications. For exploiting the space, time, and frequency diversity, the low-density parity-check code (LDPC) is used as a channel coding with a built-in interleaver. The receiver employs the expectation maximization (EM) algorithm so as to perform the MAP symbol detection with reasonable computational complexity. The minimum mean square error (MMSE), recursive least squares (RLS), and least mean square (LMS) algorithms are theoretically derived for the channel estimation within this framework. Furthermore, the proposed receiver performs a new scheme called backward symbol detection (BSD), in which the signal detection uses the channel impulse response that is estimated one OFDM symbol later. The advantage of BSD, which is explained from the viewpoint of the message passing algorithm, is that BSD can exploit information on the both precedent and subsequent OFDM symbols, similarly to RLS with smoothing and removing (SR-RLS) [25]. In comparison with SR-RLS, BSD reduces the complexity at the cost of packet error rate (PER) performance. Computer simulations show that the receiver employing RLS for the channel estimation outperforms the ones employing MMSE or LMS, and that BSD can improve the PER performance of the ones employing RLS or LMS.

The UWB (ultra-wideband) pulse radar is a promising candidate as an environment measurement method for rescue robots. Radar imaging to locate a nearby target is known as an ill-posed inverse problem, on which various studies have been done. However, conventional algorithms require long computational time, which makes it difficult to apply them to real-time operations of robots. We have proposed a fast radar imaging algorithm, the SEABED algorithm, for UWB pulse radars. This algorithm is based on a reversible transform, BST (Boundary Scattering Transform), between the target shape and the observed data. This transform enables us to estimate target shapes quickly and accurately in a noiseless environment. However, in a noisy environment the image estimated by the SEABED algorithm is degraded because BST utilizes differential operations. We have also proposed an image stabilization method, which utilizes the upper bound of the smoothness of received data. This method can be applied only to convex objects, not to concave ones. In this paper, we propose a fractional BST, which is obtained by expanding the conventional BST, and an image stabilization method by using the fractional BST. We show that the estimated image can be stabilized regardless of the shape of target.

This paper introduces a new graph problem to find an Optimal Euler Circuit (OEC) in an Euler graph. OEC is defined as the Euler circuit that maximizes the sum of contiguous costs along it, where the contiguous cost is assigned for each of the two contiguous edges incident to a vertex. We prove that the OEC problem is NP-complete. A polynomial time algorithm will be presented for the case of a graph without vertex of degree greater than 4, and for the general case, a 1/4-approximation polynomial time algorithm will be proposed.

While web proxy caching is a widely deployed technique, the performance of a proxy cache is limited by the local storage. Some studies have addressed this limitation by using the residual resources of clients via a p2p method and have achieved a very high hit rate. However, these approaches treat web objects as homogeneous objects and there is no consideration of various web characteristics. Consequently, the byte hit rate of the system is limited, external bandwidth is wasted, and perceived user latency is increased. The present paper suggests an efficient p2p based web caching technique that manages objects with different policies so as to exploit the characteristics of web objects, such as size and temporal locality. Small objects are stored alone whereas large objects are stored by dividing them into numerous small blocks, which are distributed in clients. On a proxy cache, header blocks of large objects take the place of objects themselves and smaller objects are cached. This technique increases the hit rate. Unlike a web cache, which evicts large objects as soon as possible in the case where clients fulfill the role of backup storage, large objects are given higher priority than small objects in the proposed approach. This maximizes the effect of hits for large objects and thereby increases the byte hit rate. Furthermore, we construct simple latency models for various p2p based web caching systems and analyze the effects of the proposed policies on these systems. We then examine the performances of the efficient policies via a trace driven simulation. The results demonstrate that the proposed techniques effectively enhance web cache performance, including hit rate, byte hit rate, and response time.

In this paper, we present a modified genetic algorithm for solving combinatorial optimization problems. The modified genetic algorithm in which crossover and mutation are performed conditionally instead of probabilistically has higher global and local search ability and is more easily applied to a problem than the conventional genetic algorithms. Three optimization problems are used to test the performances of the modified genetic algorithm. Experimental studies show that the modified genetic algorithm produces better results over the conventional one and other methods.

Using a pair of matched square-root-raised-cosine (SRRC) filters in the transmitter and the receiver in a band-limited digital communication system can theoretically achieve zero inter-symbol interference (ISI). In reality, the ISI cannot be zero when both SRRC filters are approximately implemented because of some numerical precision problems in the design phase as well as in the implementation phase. In this paper, the author proposes an iterative method to design the coefficients of SRRC FIR filters. The required ISI of the system can be specified such that both ISI and frequency domain specifications are monitored in the design phase. Since the ISI can be specified beforehand, the tradeoff between performance and the filter length becomes possible in the proposed design algorithm.

In this paper, we propose a modified reproduction strategy of a Genetic Algorithm (GA) utilizing a Self-Organizing Map (SOM) with a novel updating rule of binary weight vectors based on a significance of elements of inputs. In this rule, an updating order of elements is decided by considering fitness values of individuals in a population. The SOM with the proposed updating rule can realize an effective reproduction.