Construction of asymmetric connectors of depth two

Ahlswede R, Aydinian H (2006)
Journal of Combinatorial Theory. Series A 113(8): 1614-1620.

Download
Es wurde kein Volltext hochgeladen. Nur Publikationsnachweis!
Zeitschriftenaufsatz | Veröffentlicht | Englisch
Abstract / Bemerkung
An (n, N)-connector of depth d is an acyclic digraph with n inputs and N outputs in which for any injective mapping of input vertices into output vertices there exist n vertex disjoint paths of length at most d joining each input to its corresponding output. In this paper we consider the problem of construction of sparse depth two connectors with n << N. We use posets of star products and their matching properties to construct such connectors. In particular, this gives a simple explicit construction for connectors of size O(N log n/log log n). Thus our earlier idea to use other posets than the family of subsets of a finite set was successful. (c) 2006 Elsevier Inc. All rights reserved.
Erscheinungsjahr
Zeitschriftentitel
Journal of Combinatorial Theory. Series A
Band
113
Ausgabe
8
Seite(n)
1614-1620
ISSN
PUB-ID

Zitieren

Ahlswede R, Aydinian H. Construction of asymmetric connectors of depth two. Journal of Combinatorial Theory. Series A. 2006;113(8):1614-1620.
Ahlswede, R., & Aydinian, H. (2006). Construction of asymmetric connectors of depth two. Journal of Combinatorial Theory. Series A, 113(8), 1614-1620. doi:10.1016/j.jcta.2006.03.009
Ahlswede, R., and Aydinian, H. (2006). Construction of asymmetric connectors of depth two. Journal of Combinatorial Theory. Series A 113, 1614-1620.
Ahlswede, R., & Aydinian, H., 2006. Construction of asymmetric connectors of depth two. Journal of Combinatorial Theory. Series A, 113(8), p 1614-1620.
R. Ahlswede and H. Aydinian, “Construction of asymmetric connectors of depth two”, Journal of Combinatorial Theory. Series A, vol. 113, 2006, pp. 1614-1620.
Ahlswede, R., Aydinian, H.: Construction of asymmetric connectors of depth two. Journal of Combinatorial Theory. Series A. 113, 1614-1620 (2006).
Ahlswede, Rudolf, and Aydinian, Haratyun. “Construction of asymmetric connectors of depth two”. Journal of Combinatorial Theory. Series A 113.8 (2006): 1614-1620.