Stable networks and product graphs / Tomas Feder.

Format:

Book

Author/Creator:

Feder, Tomás, author.

Series:

Memoirs of the American Mathematical Society ; Volume 116, Number 555.

Memoirs of the American Mathematical Society, 0065-9266 ; Volume 116, Number 555

Language:

English

Subjects (All):

Machine theory.

Graph theory.

System analysis.

Physical Description:

1 online resource (242 p.)

Edition:

1st ed.

Place of Publication:

Providence, Rhode Island : American Mathematical Society, 1995.

Language Note:

English

Summary:

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.

Contents:

""Contents""; ""Abstract""; ""Acknowledgements""; ""1 Introduction""; ""1.1 Organization""; ""2 Preliminaries""; ""2.1 Gates, Circuits, and Networks""; ""2.1.1 Modifying a Network""; ""2.2 Evaluation, Convergence, and Stability""; ""2.3 Classification of Bases""; ""2.3.1 Universal Bases""; ""2.3.2 Linear Bases""; ""2.3.3 Monotone Bases""; ""2.4 Nonexpansive Bases""; ""2.4.1 No Finite Basis for Nonexpansive Gates""; ""2.4.2 Circuits and Networks with Variable Inputs""; ""2.5 Complexity Assumptions""; ""3 Stability in Nonexpansive Networks""; ""3.1 Hamming Distance and Convergent Networks""

""3.1.1 Convergent Networks""""3.1.2 Properties of Convergent Networks""; ""3.1.3 Algorithms for Convergent Networks""; ""3.1.4 Representation by Convergent Networks""; ""3.1.5 Algorithms for Stability""; ""3.1.6 Randomized Algorithms""; ""3.1.7 Lower Bounds""; ""3.2 Fixed Points and Retracts""; ""3.2.1 Fixed Points and Medians""; ""3.2.2 Median Sets and 2SAT""; ""3.2.3 Representation by Circuits""; ""3.3 Periodic Points and Isomorphisms""; ""3.3.1 Distances and Periodic Points""; ""3.3.2 Efficient Representation of Stable Configurations""

""3.3.3 Efficient Representation in Scatter-Free Networks""""3.4 Unstable Networks and Fixed Cubes""; ""3.4.1 Minimal Fixed Cubes""; ""3.4.2 Algorithms for Fixed Cubes""; ""3.4.3 From Monte Carlo to Las Vegas""; ""3.4.4 A Small Certificate for Mappings without Fixed Point""; ""3.4.5 The Convergent Network Representation is Decidable""; ""3.4.6 Convergent Network Evaluation and Linear Programming""; ""3.5 Non-Periodic Points and Iterates""; ""3.5.1 The Scatter-Free Case""; ""3.5.2 The Nonexpansive Case""; ""3.5.3 Evaluation, Stability and Convergence""; ""3.6 Discussion""

""4. Optimization and Enumeration""""4.1 Uncapacitated Flow""; ""4.1.1 Flow Problems and Width""; ""4.1.2 Maximum Flow when the Width is Small""; ""4.1.3 Maximum Flow when the Optimum is Small""; ""4.1.4 Uncapacitated Blocking Flow""; ""4.2 Optimization on 2SAT instances""; ""4.2.1 The Non-Bipartite Case""; ""4.2.2 The Bipartite Case""; ""4.3 Enumeration on 2SAT instances""; ""4.4 Discussion""; ""5 Stable Matching""; ""5.1 The Stable Arrangement Problem""; ""5.1.1 Stable Arrangements""; ""5.1.2 Reduction to Network Stability""; ""5.1.3 Instabilities and Local Search""

""5.1.4 Structural Properties""""5.1.5 Complexity of Several Arrangement Problems""; ""5.2 Optimization and Enumeration in Stable Matching""; ""5.2.1 Size and Width""; ""5.2.2 Optimization""; ""5.2.3 Enumeration and Partial Arrangements""; ""5.3 Discussion""; ""6 Metric Networks and Product Graphs""; ""6.1 Metric Spaces""; ""6.2 Representations""; ""6.3 Isometric Representation""; ""6.4 Prime Factorization""; ""6.5 The 2-Isometric Representation""; ""6.5.1 Closed Sets and the Imprint Function""; ""6.5.2 2-Isometric Subspaces""; ""6.5.3 2-Isometric Representations""; ""6.6 Retracts""

""6.6.1 Subspaces without Holes and the Distance Center""

Notes:

Description based upon print version of record.

Includes bibliographical references and index.

Description based on print version record.

ISBN:

1-4704-0134-7