Memoirs of the American Mathematical Society 1995; 223 pp; softcover Volume: 116 ISBN10: 0821803476 ISBN13: 9780821803479 List Price: US$54 Individual Members: US$32.40 Institutional Members: US$43.20 Order Code: MEMO/116/555
 A network is a collection of gates, each with many inputs and many outputs, where links join individual outputs to individual inputs of gates; the unlinked inputs and outputs of gates are viewed as inputs and outputs of the network. A stable configuration assigns values to inputs, outputs, and links in a network, to ensure that the gate equations are satisfied. The problem of finding stable configurations in a network is computationally hard. In this work, Feder restricts attention to gates that satisfy a nonexpansiveness condition requiring small perturbations at the inputs of a gate to have only a small effect at the outputs of the gate. The stability question on the class of networks satisfying this local nonexpansiveness condition contains stable matching as a main example, and defines the boundary between tractable and intractable versions of network stability. Readership Research mathematicians. Table of Contents  Abstract
 Acknowledgements
 Introduction
 Preliminaries
 Stability in nonexpansive networks
 Optimization and enumeration
 Stable matching
 Metric networks and product graphs
 Bibliography
 Index
