On finding spanning eulerian subgraphs

In this article, we examine the problem of producing a spanning Eulerian subgraph in an undirected graph. After the ?-completeness of the general problem is established, we present polynomial-time algorithms for both the maximization and minimization versions where instances are defined on a restricted class of graphs referred to as series-parallel. Some novelties in the minimization case are discussed, as are heuristic ideas.     

Interception in a network

This paper presents an algorithm for determining where to place intercepting units in order to maximize the probability of preventing an opposing force from proceeding from one particular node in an undirected network to another. The usual gaming assumptions are invoked; namely, the strategy for placing the units is known to the opponent and he will choose a path through the network which, based on this knowledge, maximizes his probability of successful traverse. As given quantities, the model requires a list of the arcs and nodes of the network, the number of intercepting units available to stop the opposing force, and the probabilities for stopping the opposition at the arcs and nodes as functions of the number of intercepting units placed there. From these quantities, the algorithm calculates the probabilities for placing the unit at the arcs and nodes when one intercepting unit is available, and the expected numbers of units to place at the arcs and nodes when multiple intercepting units are available.     

Book Reviews

Strategic Air Defense. Edited by Stephen J. Cimbala. Scholarly Resources, Wilmington, DE (1989), ISBN 0–8420–2285–6, $40.00

NATO's Defence of the North. Brassey's Atlantic Commentaries No. 1. Edited by Eric Grove. Brassey's, London (1989), ISBN 0–08–037339–9, £7.50

Maritime Strategy and the Balance of Power: Britain and America in the Twentieth Century. Edited by John B. Hattendorf and Robert S. Jordan. Macmillan, London (1989), ISBN 0–333–43789–6, £45.00

Superpowers at Sea: an Assessment of the Naval Arms Race. By Richard Fieldhouse and Shunji Taoka. SIPRI, Oxford (1989), ISBN 0–19–829135–3

Security at Sea: Naval Arms Control. Edited by Richard Fieldhouse. Oxford University Press, Oxford (1990), ISBN 0–19–829130–2, £25.00

Strategy in the Southern Oceans: a South American View. By Virginia Gamba‐Stonehouse. Pinter, London (1989), ISBN 0–86187–017–4, £30.00

The Defence Industrial Base and the West. Edited by D. G. Haglund. Routledge, London (1989), ISBN 0–415–00923–5, £30.00

Defense and Détente: US and West German Perspectives on Defense Policy. Edited by Joseph I. Coffey and Klaus von Schubert. Westview Press, Boulder, CO, ISBN 0–8133–7722–6, $36.50     

Book reviews

War, Culture and the Media: Representations of the Military in 20th Century Britain. Edited by Ian Stewart and Susan L. Carruthers, Trowbridge: Flicks Books, (1996), ISBN 0-948911-86-7 (pbk), £14.95.

The Future of Europe. By Peter Coffey, Aldershot: Edward Elgar, (1995), ISBN 1-85278-586-1 (hardback), £39.95, ISBN 1-85278-587-X (pbk), £12.95.

Global Dangers: Changing Dimensions of International Security. Edited by Sean M. Lynn-Jones, Steven E. Miller, London: the MIT Press, (1996), ISBN O-262-62097-9 (pbk), £13.50;.

New Studies in Post-Cold War Security. Edited by K.R. Dark, Aldershot: Dartmouth Publishing Company, (1996), ISBN 1-85521-728-7 (hardback), £42.50.

Enlarging NATO - The Russian Factor. By Richard L. Kugler with Marianna V. Kozintseva, Santa Monica, CA: National Defense Research Institute and Rand Corporation, (1996), ISBN 0-8330-2357-8, $20.00.     

Cumulative search-evasion games

Cumulative search-evasion games (CSEGs) are two-person zero-sum search-evasion games where play proceeds throughout some specified period without interim feedback to either of the two players. Each player moves according to a preselected plan. If (X_t, Y_t,) are the positions of the two players at time t, then the game's payoff is the sum over t from 1 to T of A(X_t, Y_t, t). Additionally, all paths must be “connected.” That is, the finite set of positions available for a player in any time period depends on the position selected by that player in the previous time period. One player attempts to select a mixed strategy over the feasible T-time period paths to maximize the expected payoff. The other minimizes. Two solution procedures are given. One uses the Brown-Robinson method of fictitious play and the other linear programming. An example problem is solved using both procedures.     

Estimation and prediction in a semi-markov model for evasive vehicle movement along a fixed path

In Turner and Holmes [8] a model for evasive vehicle movement along a fixed track is developed within the mathematical framework of a two-state semi-Markov process. They derive a number of analytical properties of the model. In this article we address problems concerning the estimation of parameters in the model and the construction of data-based prediction equations.     

Location of facilities with rectangular distances among point and area destinations

This article is concerned with the optimal location of any number (n) of facilities in relation to any number (m) of destinations on the Euclidean plane. The criterion to be satisfied is the minimization of total weighted distances where the distances are rectangular. The destinations may be either single points, lines or rectangular areas. A gradient reduction solution procedure is described which has the property that the direction of descent is determined by the geometrical properties of the problem.     

An optimum t-test for the scale parameter of an extreme-value distribution

A Student's t-test proposed by Ogawa is considered for the hypothesis Ho: σ=σo against the alternative hypothesis H₁: σ ≠ σo, where σ is the scale parameter of the Extremevalue distribution of smallest values with known location parameter μ. The test is based on a few sample quantiles chosen from a large sample so as to give asymptotically maximum power to the test when the number of sample quantiles is fixed. A table which facilitates the computation of the test statistic is given. Several schemes for determining the ranks of the sample quantiles by the optimal spacings are compared and the effect of the bias of the estimate of σ on the test is investigated through a Monte Carlo study.