If π is a monotone property on graphs (that is, π is attainable by adding edges to a given graph), then the graph augmentation problem with respect to π is defined by: "Given a graph G=(V, E) and nonnegative weights w(u, v) for all pairs {u, v} VV (uv), find an edge set Eof minimum total weight such that the graph G=(V, EE) satisfies π, where we assume that w(u, v)=0 for every edge (u, v) E". The subject of the paper is to give an overview of the graph augmentation problems where π is concerned with vertex-or edge-connectivity of graphs. Also presented are basic ideas used in solving this problem.

In this paper, we consider an automatic warehouse, in which rc-k palettes are arranged two-dimensionally on a grid with r rows c columns. The palettes in the warehouse can slide independently and simultaneously with the use of k spaces, unless they come into collision. Then, we show the minimum number of sliding operations required to move a specified palette to a specified position, where one sliding operation is a set of slides of palettes which are executed simultaneously in a unit time withouto any collision.

This paper shows that the strong Minkowski decomposition problem is NP-complete. Given two convex polygons α and β, the Minkowski sum α+β is a convex polygon defined by {(a_x+b_x, a_y+b_y|(a_x+a_y)α, (b_xb_y)β}. The Minkowski decomposition problem is for a given convex polygon γ to find two non-trivial convex polygons α and β whose Minkowski sum is γ. Silverman and Stein gave a linear-time algorithm for this problem. The strong Minkowski decomposition problem is to decompose a given convex polygon into two convex polygons in such a way that any pair of edges of two polygons are not in parallel. It is well known that the Minkowski sum of two convex polygons can be computed in linear time with respect to the number of edges involved. The NP-completeness result of the strong Minkowski decomposition problem shows interesting contrast to the following two results: One is that its inverse operation, the Minkowski sum operation, can be computed in linear-time; Another result, recently obtained by Mount and Silverman, is that the strong Minkowski operation for a convex polyhedron in R³ is also linear-time computable.

In this paper we present polynomial time algorithms for the following three problems on a Hamilton graph with a prescribed Hamilton circuit: (1) Given a Hamilton graph G with a prescribed Hamilton circuit, find a maximal planar Hamilton subgraph of G, (2) Given a Hamilton graph G and a planar Hamilton subgraph H of G, find a maximal planar Hamilton subgraph of G that contains H, and (3) Given an edge-weighted Hamilton graph G=(V, E), find a planar Hamilton subgraph G=(V, E) of G such that the addition of an edge e E-Edestroys the planarity, unless we delete an edge from Ehaving no less weight than e. The time complexities of the algorithms are O(n+m), O(m^3/2) and O(m^5/3), respectively, where n(resp., m) is the number of vertices (resp., edges) of the Hamilton graph. These algorithms are applicable to the Topological Via Minimization problem.

This paper gives an O(n log n)-time algorithm for the following problem: min Σⁿ_i=1|x_i-a_i| s.t.x₁x₂x_n where a_i(i=1, , n) are given constants and x_i(i=1, , n) are variables. There has been given an O(n²)-time incremental algorithm, and we improve it by using the heap as a data structure and modify the incremental algorithm partly. This problem is a kind of the geometric fitting problem between two corresponding sets of points on a line which is related to some VLSI layout design problem.

The paper proves the polynomiality of the multiplicative penalty function method for linear programming proposed by Iri and Imai. This is accomplished by considering ellipsoids determined by the Hessian at an interior point and centered at the point, and showing that, for any interior point, there is such an ellipsoid contained in the feasible region in which the penalty function is well approximated by a linear function determined by the gradient at the point.

In location problems, the outtransmission and intransmission numbers are important indices to evaluate a directed network. We formulate and consider a new problem of fault diagnosis in a system modeled by a directed network in which to each edge a positive real number called the length of edge is assigned and to each vertex a positive real number called the weight of vertex is assigned. By a fault in a directed network, we mean any increase in the length of an edge with respect to its nominal length. A theory and an algorithm for detecting a fault edge in a directed network in which the above indices, i.e. outtransmission and/or intransmission numbers, are measurable, are presented.

For a given 2-edge-connected graph G and a spanning tree T of G, the graph augmentation problem 2ECA (T,G) is to find a minimum edge set AE (G) such that T A is 2-edge-connected. This note proves that 2ECA (T, G) is solvable in polynomial time if G is series-parallel.

We present an algorithm for finding a maximum weight independent set of a circle graph. For a cicle graph of a set of n chords with N endpoints, the algorithm finds a maximum weight independent set in O(nN) time and O(n) space.

Consider a connected network N. With each edge of N we associate a nonnegative real number called the length of the edge. Let N be a network obtained from N by adding new edges and/or by decreasing the lengths of some edges. For a generalized transmission number c_f(N, v) defined on vertex v in N, we call Δ_c(v)=c_f(N, v)-c_f(N ,v) the Sabidussi difference of vertex v. In this note, we present a new theorem and its corollaries on the Sabidussi difference.

We introduce the distance between two edges in a graph (nondirected graph) as the minimum number of edges in a tieset with the two edges. Using the distance between edges we define the eccentricity ε_τ (e_j) of an edge e_j. A finite nonempty set J of positive integers (no repetitions) is an eccentric set if there exists a graph G with edge set E such that ε_τ (e_j) J for all e_i E and each positive integer in J is ε_τ (e_j) for some e_j E. In this paper, we give necessary and sufficient conditions for a set J to be eccentric.

In audio teleconference systems, speech quality may be degraded due to acoustic echo in the conference room. Echo control devices, such as echo cancellers, can be used to improve the speech quality. This paper describes the echo return loss required for acoustic echo controllers used in audio teleconferencing based on subjective assessment. In particular, far-end or talker echo is subjectively evaluated using a simulated audio teleconference system constructed in our laboratory. Test conditions are given as combinations of transmission delay and insertion loss. The subjective tests were also evaluated under three different reverberation times of echo path. The thresholds of detectable and/or objectionable echoes and mean opinion score in view of acoustic echo and reverberation in audio teleconferencing are clarified. From this, we can ascertain that an echo objection limit that 90% of the subjects consider to be permissible leads to a required echo return loss of more than 40 dB when the overall round-trip delay time T_ord is 100 ms and the reverberation time T_rev is 400 ms.

The effect of multiple classes of the arrival messages on the resequencing delay for a queueing system with multiple servers of possibly different service rates under a threshold-type scheduling is analyzed. We first derive the general expressions for the mean resequencing delay for the M/M/n queueing system shared by C different classes of the arrival messages under a threshold-type scheduling. Next, the numerical calculation is carried out for the queueing system with 3 servers under a threshold-type scheduling to consider the effect of the multiple message classes on the mean total delay including the resequencing delay. It is found that the total delay is decreased as the number of message classes is increased, and that the total delay is minimized when the message classes are equally distributed. It is also found that the system under a threshold-type scheduling for multiple message classes is more effective to reduce the total delay and is less sensitive to the variation of the message class distribution.

This paper approximations to the transient probabilities P_ij (t) (i, j=0, 1, 2, , n) for a transition from state i at t=0 to state j at time t in the n-channel birthdeath processes. First, P_0n(t) is considered as an extension of Gnedenko's approximate expressions when state n is regarded as an absorbing state for the models M/M/1/n/, M/M/1/n/N, M/M/n/n/, and M/M/n/n/N. That is to say, if P_n is the steady-state probability of state n, the approximations P_0n(t)/P_n when state n is not an absorbing state can be obtained from the function 1-exp{-Q(t)} (Q(t)0 is an analytic function). Based on these considerations, transition diagrams are derived to obtain P_0n (t) for the models M/M/S/n/ and M/M/S/n/N. Finally, P_ij(t) can be expressed with this P_0n(t). Several examples show that the approximations of the transient probabilities are nearly equal to the exact values calculated numerically using the Runge-Kutta method on a personal computer. As the approximations in this paper are very precise and calculable instantaneously on a personal computer, they may be applicable for time-dependent traffic theory which will be useful, for instance, in real-time network management technology.

A new algebraic solution is developed for nonlinear integral/ differential equations including power-law or product-type nonlinearities. The new method performs the computation via PL transform using multiplication operator with the aid of integral operator through iterative calculations. This method is capable of solving integral or integro-differential equations without converting the equation into a equivalent differential equation. The method is also capable of solving higher-order differential equations without converting the equation into a set of simultaneous first order differential equations. Examples show that a good accuracy was obtained using a limited length PL transform through a small number of iterations.

In this paper, we will propose a modified Euclidean algorithm which can be obtained by examining thoroughly the equivalence between conventional Euclidean algorithm and Berlekamp-Massey algorithm. Furthermore, we will show the design method for BCH decoders and Inverters based on the modified Euclidean algorithm in which the minimum number register realization is given.