登入選單
返回Google圖書搜尋
Stable Networks and Product Graphs
Tomás Feder
出版American Mathematical Soc., 1995
主題Computers / Machine TheoryMathematics / GeneralMathematics / AppliedMathematics / Discrete MathematicsMathematics / Graphic MethodsMathematics / LogicMathematics / CombinatoricsScience / System Theory
ISBN08218034769780821803479
URLhttp://books.google.com.hk/books?id=KW3TCQAAQBAJ&hl=&source=gbs_api
EBookSAMPLE
註釋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 non-expansiveness 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 non-expansiveness condition contains stable matching as a main example, and defines the boundary between tractable and intractable versions of network stability.