In the past three years several new Soviet high-performance computers have been announced and a number of earlier models have been approved for series production. These models represent the most innovative computer design work in the USSR. Some of the technical characteristics of these machines are reviewed. The following machines are examined: EL 'brus; PS-2000, PS-2100; ES-2704, ES-2727; ES-2701; ES-2703; ES-1181; ES-1191; and loosely coupled array processor machines. It is pointed out that the perestroika reforms have not greatly helped, and in many cases have harmed., the high-performance computing industry.>

The "national presence" of the information technologies in Soviet society differs somewhat, both quantitatively and qualitatively, from that in the US and other large industrialized Western countries. This presence is described and assessed by considering: 1) current Soviet capabilities and recent initiatives to improve those capabilities; 2) a model of a "Soviet-style information society" and its comparison with an analogous model for the West; 3) prospective progress and problems to the end of the century within the context of our model; and 4) boundaries, including the probable limits of systemic evolution for Soviet society, and the extent to which the boundaries of our model are being or are likely to be reached or crossed.

Abstract An algorithm is presented which solves the problem of finding the longest simple cycle in an undirected edge‐weighted network. The properties of the vector spaces associated with the fundamental cycles of a network are used to develop a suitable algorithm for finding simple cycles, and this is imbedded into a branch and bound scheme that solves the longest cycle problem.

Abstract The Optional Hamiltonian Completion Problem is defined as follows: let the points V of a graph G be partitioned into a set V0 of optional points and a set V1 of non‐optional points; determine the minimum number of new lines which when added to G result in a graph which has a cycle containing every point of V1. This cycle may or may not contain optional points of V0. In this paper we present algorithms for solving this problem for trees, unicyclic graphs and cacti.

We develop linear-time algorithms to find maximum weighted and unweighted degree-constrained subgraphs (b-matchings) of a tree. We use a generalization of an algorithm for finding a maximum 2-matching in a tree.

article Free Access Share on Advances on the Hamiltonian Completion Problem Authors: S. E. Goodman Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , S. T. Hedetniemi Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VA Department of Applied Mathematics and Computer Science, University of Virginia, Charlottesville, VAView Profile , P. J. Slater National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, Iowa National Bureau of Standards, Washington, DC and University of Iowa, Iowa City, IowaView Profile Authors Info & Claims Journal of the ACMVolume 22Issue 3July 1975 pp 352–360https://doi.org/10.1145/321892.321897Published:01 July 1975Publication History 18citation522DownloadsMetricsTotal Citations18Total Downloads522Last 12 Months18Last 6 weeks3 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A Hamiltonian walk in a graph G is a closed walk of minimum length which contains every point of G. An Eulerian walk in a graph G is a closed walk of minimum length which contains every line of G. In this paper we establish several relationships between Hamiltonian and Eulerian walks. We also derive a number of bounds on the length of a Hamiltonian walk.

The general problem of finding the shortest edge covering walks in an arbitrary undirected graph is investigated. An exact combinatoric expression is obtained for the length of such a walk, and the graph theoretic properties of these walks are studied. Explicit solutions are exhibited for some important classes of graphs.