Stable Networks and Product Graphs
( Memoirs of the American Mathematical Society )
Publication series ：Memoirs of the American Mathematical Society
Author： Tom(’)as Feder
Publisher： American Mathematical Society
Publication year： 2013
E-ISBN: 9781470401344
P-ISBN(Paperback): 9780821803479
Subject： O141 (mathematical logic) symbolic logic.
Keyword： Applications
Language： ENG
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Stable Networks and Product Graphs
Description
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.