As IT systems grow bigger and complex, they are comprised of many resources supplied by various vendors. Also, the Internet accelerates inter-enterprise business transactions and IT systems are connected each other. Consequently enterprise application systems are becoming a kind of large business process across multiple vendors. This transformation will also bring new type of complexity and difficulties to enterprise IT system management. Having awareness of these issues, IBM and Fujitsu have been collaborating on standardization effort for various areas of autonomic computing technologies. Autonomic computing and open standard interface are an effective approach to deal with these challenges. The initial areas of collaboration are common event format and interface for action to manage IT resources. hi this presentation, we show how an autonomic manager can solve these issues with using an open standard, WSDM (Web Service Distributed Management). We demonstrate the autonomic manager that behaves based on defined policy, continuously monitors systems, handles events and takes actions through WSDM interface in Multi-vendor IT Systems.

We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total weight of a minimum structure on P is maximized. In particular, we are interested in three problems of this type, where the structure to be minimized is a spanning tree ({\sc Remote-MST}), Steiner tree, or traveling salesperson tour. We study a natural greedy algorithm that simultaneously approximates all three problems on metric graphs. For instance, its performance ratio for {\sc Remote-MST} is exactly 4, while this problem is NP-hard to approximate within a factor of less than 2. We also give a better approximation for graphs induced by Euclidean points in the plane, present an exact algorithm for graphs whose distances correspond to shortest-path distances in a tree, and prove hardness and approximability results for general graphs.

Abstract LetG = (V, E)be an undirected graph withnvertices andmedges such that a real‐valued weight, denoted byw(e), is associated with each edgee. This paper studies what we call the minimum range cut problem that asks to find a cut inGsuch that the range of all edge weights in the cut is minimum. Here, the range of a cutCis defined to be the maximum difference among weights of edges in the cut, i.e., maxeϵcw(e)‐ mineϵcw(e). This paper proposes anO(m + nlogn) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum ranges – tcut problem that asks to find ans – tcut with minimum range. This paper proposesO(m + nlogn) algorithms for these problems. For the second problem, we show that anancestor treeofO(n)space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed inO(n2)time, and enables us to answer any minimum ranges – tcut query inO(1)time [resp., inO(n)time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). © 1994 by John Wiley & Sons, Inc.

We study the problem of enumerating k farthest pairs for n points in the plane and the problems of enumerating k closest/farthest bichromatic pairs of n red and n blue points in the plane. We propose a new technique for geometric enumeration problems which iteratively reduces the search space by a half and provides efficient algorithms. As applications of this technique, we develop algorithms, using higher order Voronoi diagrams, for the above problems, which run in O(min{n2, n log n + k4/3 log n/log1/3k}) time and O(n+k4/3/(log k)1/3+k log n) space. Since, to the authors' knowledge, no nontrivial algorithms have been known for these problems, our algorithms are currently fastest when k=o(n3/2).

The authors investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Suppose that one is given a set of n points in general d-dimensional space, S=(p/sub 1/,p/sub 2/, . . ., p/sub n/), and that all points move along different straight lines at different but fixed speeds, i.e., the position of p/sub i/ is a linear function of a real parameter. They investigate the numbers of transitions of MinST and MaxST when t increases from - infinity to + infinity . They assume that the dimension d is a fixed constant. Since there are O(n/sup 2/) distances among n points, there are naively O(n/sup 4/) transitions of MinST and MaxST. They improve these trivial upper bounds for L/sub 1/ and L/sub infinity / distance metrics. Let c/sub p/(n, min) (resp. c/sub p/(n, max)) be the number of maximum possible transitions of MinST (resp. MaxST) in L/sub p/ metric for n linearly moving points. They give the following results; c/sub 1/(n, min)=O(n/sup 5/2/a(n)), c/sub infinity /(n, min)=O(n/sup 5/2/a(n)), c/sub 1/(n, max)=O(n/sup n/) and c/sub infinity /(n, max)=O(n/sup 2/) where O(n) is the inverse Ackermann function. They also investigate two restricted cases.>

Two natural operations on the set of convex polygons are shown to form a closed semiring; the two operations are vector summation and convex hull of the union. Various properties of these operations are investigated. Kleene’s algorithm applied to this closed semiring solves the problem of determining whether a directed graph with two-dimensional labels has a zero-sum cycle or not. This algorithm is shown to run in polynomial time in the special cases of graphs with one-dimensional labels, BTTSP (Backedged Two-Terminal Series-Parallel) graphs, and graphs with bounded labels. The undirected zero-sum cycle problem and the zero-sum simple cycle problem are also investigated.

Abstract This paper describes an efficient way to test the VAP‐free (Vertex Accumulation Point free) planarity of one‐ and two‐dimensional dynamic graphs. Dynamic graphs are infinite graphs consisting of an infinite number of basic cells connected regularly according to labels in a finite graph called a static graph. Dynamic graphs arize in the design of highly regular VLSI circuits, such as systolic arrays and digital signal processing chips. We show that VAP‐free planarity testing of dynamic graphs can be done efficiently by making use of their regularity. First, we will establish necessary conditions for VAP‐free planarity of dynamic graphs. Then we show the existence of a small finite graph which is planar if and only if the original dynamic graph is VAP‐free planar. From this it follows that VAP‐free planarity testing of one‐ and two‐dimensional dynamic graphs is asymptomically no more difficult than planarity testing of finite graphs, and thus can be done in linear time.

Article Free Access Share on Testing for cycles in infinite graphs with periodic structure Authors: K. Iwano Dept. of Computer Science, Rinceton University, Plrinceton, NJ Dept. of Computer Science, Rinceton University, Plrinceton, NJView Profile , K. Steiglitz Dept. of Computer Science, Rinceton University, Plrinceton, NJ Dept. of Computer Science, Rinceton University, Plrinceton, NJView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 46–55https://doi.org/10.1145/28395.28401Published:01 January 1987Publication History 23citation426DownloadsMetricsTotal Citations23Total Downloads426Last 12 Months37Last 6 weeks6 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We study the problem of optimizing the pulldown diffusion widths in the one-bit full adder when it is embedded in a regular array, using the simplest possible array multiplier with a delay-time criterion as an example. A local optimization algorithm is used, which varies two parameters at a time along the critical path until a local optimum is found. The analysis routines include the Berkeley tools [10] and the Princeton procedural layout language ALLENDE [11- 12]. Two ways are suggested for optimizing large arrays in practical amounts of time. First, the full-adder cell optimized within a minimum-size array can be used in the large array. This is a good choice because the interior cells of the small prototype have the same boundary conditions as those in the larger array. A second, even faster, method is to approximate the delay time from some simple assumptions about the critical path. Numerical results show that both these methods are effective. We give typical local optima obtained when delay time is minimized, together with power-time tradeoff curves, for the 3×3 and 4×4 array multipliers, using 4µ (λ=2µ) nMOS fabrication parameters, and a 5- parameter random-logic full-adder cell.