Einzeltreffer — DigiBib

We present randomized and deterministic algorithms for many-to-one packet routing on an n-node two-dimensional mesh under the store-and-forward model. We consider the general instance of many-to-one routing where each node is the source (resp., destination) of l (resp., k) packets, for arbitrary values of l and k. All our algorithms run in optimal O(√lkn) time and use queues of only constant size at each node to store packets in transit. The randomized algorithms, however, are simpler to implement. Our result closes a gap in the literature, where time-optimal algorithms using constant-size queues were known only for the special cases l = 1 and k=l = k.

Titel:	Optimal many-to-one routing on the mesh with constant queues
Autor/in / Beteiligte Person:	PIETRACAPRINA, Andrea ; PUCCI, Geppino
Link:	E-Journal im Bestand der UB Hagen? View record from PASCAL Archive
Zeitschrift:	Information processing letters, Jg. 96 (2005), Heft 1, S. 24-29
Veröffentlichung:	Amsterdam: Elsevier Science, 2005
Medientyp:	academicJournal
Umfang:	print, 5 ref
ISSN:	0020-0190 (print)
Schlagwort:	Computer science Informatique Sciences exactes et technologie Exact sciences and technology Sciences appliquees Applied sciences Informatique; automatique theorique; systemes Computer science; control theory; systems Informatique théorique Theoretical computing Algorithmique. Calculabilité. Arithmétique ordinateur Algorithmics. Computability. Computer arithmetics Algorithme déterministe Deterministic algorithms Algorithme optimal Optimal algorithm Algoritmo óptimo Algorithme parallèle Parallel algorithm Algoritmo paralelo Analyse algorithme Algorithm analysis Análisis algoritmo File attente Queue Fila espera Computer theory Informática teórica Maillage Grid pattern Celdarada Routage Routing Enrutamiento Réseau interconnexion Interconnection network Red interconexión Traitement information Information processing Procesamiento información Interconnection networks Mesh Packet routing Parallel algorithms
Sonstiges:	Nachgewiesen in: PASCAL Archive Sprachen: English Original Material: INIST-CNRS Document Type: Article File Description: text Language: English Author Affiliations: Dipartimento di Ingegneria dell'Informazione, Università di Padova, Via Gradenigo 6/B, 35131 Padova, Italy Rights: Copyright 2005 INIST-CNRS ; CC BY 4.0 ; Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS Notes: Computer science; theoretical automation; systems

Klicken Sie ein Format an und speichern Sie dann die Daten oder geben Sie eine Empfänger-Adresse ein und lassen Sie sich per Email zusenden.

BibTeX Citavi, JabRef, u.a.
(Literaturverwaltung)

PDF kein Volltext!
(Merkzettel, Notizen)

RIS Endnote, Citavi u.a.
(Literaturverwaltung)

MODS
(XML zur Weiterverarbeitung)

oder

Wählen Sie das für Sie passende Zitationsformat und kopieren Sie es dann in die Zwischenablage, lassen es sich per Mail zusenden oder speichern es als PDF-Datei.

Gewünschter Zitations-Stil:

oder

Bitte prüfen Sie, ob die Zitation formal korrekt ist, bevor Sie sie in einer Arbeit verwenden. Benutzen Sie gegebenenfalls den "Exportieren"-Dialog, wenn Sie ein Literaturverwaltungsprogramm verwenden und die Zitat-Angaben selbst formatieren wollen.

Optimal many-to-one routing on the mesh with constant queues