#### Title

#### Document Type

Article

#### Department

Mathematics (HMC)

#### Publication Date

1978

#### Abstract

An $n$-connector is an acyclic directed graph having $n$ inputs and $n$ outputs and satisfying the following condition: given any one-to-one correspondence between inputs and distinct outputs, there exists a set of vertex-disjoint paths that join each input to the corresponding output. It is known that the minimum possible number of edges in an $n$-connector lies between lower and upper bounds that are asymptotic to $3n\log _3 n$ and $6n\log _3 n$ respectively. A generalized $n$-connector satisfies the following stronger condition: given any one-to-many correspondence between inputs and disjoint sets of outputs, there exists a set of vertex-disjoint trees that join each input to the corresponding set of outputs. It is shown that the minimum number of edges in a generalized $n$-connector is asymptotic to the minimum number in an $n$-connector.

#### Rights Information

© 1978 Society for Industrial and Applied Mathematics

#### Recommended Citation

Pippenger, Nicholas. “Generalized Connectors.” SIAM Journal on Computing 7, no. 4 (November 1978): 510-514.