umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Constructions of Sparse Asymmetric Connectors with Number Theoretic Methods
Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
Mathematisches seminar, Christian-Albrechts-Universität zu Kiel, Germany.
2005 (Engelska)Ingår i: Networks, ISSN 0028-3045, E-ISSN 1097-0037, Vol. 45, nr 3, s. 119-124Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider the problem of connecting a set I of n inputs to a set O of N outputs (n ≤ N) by as few edges as possible such that for every injective mapping f : I → O there are n vertex disjoint paths from i to f(i) of length k for a given k . For k = Ω(log N + logn) Oruς (1994) gave the presently best (n,N)-connector with O(N+n·log n) edges. For k=2 and N the square of a prime, Richards and Hwang (1985) described a construction using edges. We show by a probabilistic argument that an optimal (n,N)-connector has Θ (N) edges, if for some ε>0. Moreover, we give explicit constructions based on a new number theoretic approach that need at most edges for arbitrary choices of n and N. The improvement we achieve is based on applying a generalization of the Erdös-Heilbronn conjecture on the size of restricted sums.

Ort, förlag, år, upplaga, sidor
John Wiley & Sons, 2005. Vol. 45, nr 3, s. 119-124
Nyckelord [en]
connector, rearrangeable network, sparse switch, permuter, combinatorial number theory, restricted sums
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-83129DOI: 10.1002/net.20058OAI: oai:DiVA.org:umu-83129DiVA, id: diva2:665017
Tillgänglig från: 2013-11-18 Skapad: 2013-11-18 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Jäger, Gerold

Sök vidare i DiVA

Av författaren/redaktören
Jäger, Gerold
I samma tidskrift
Networks
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 363 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf