dc.contributor.author | Busch, Costas | en |
dc.contributor.author | Magdon-Ismail, M. | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.contributor.author | Spirakis, Paul G. | en |
dc.creator | Busch, Costas | en |
dc.creator | Magdon-Ismail, M. | en |
dc.creator | Mavronicolas, Marios | en |
dc.creator | Spirakis, Paul G. | en |
dc.date.accessioned | 2019-11-13T10:38:50Z | |
dc.date.available | 2019-11-13T10:38:50Z | |
dc.date.issued | 2006 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53661 | |
dc.description.abstract | Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be delivered to their destinations without collisions. We give a general treatment of three facets of direct routing: 1. Algorithms. We present a polynomial-time greedy direct algorithm which is worst-case optimal. We improve the hound of the greedy algorithm for special cases, by applying variants of this algorithm to commonly used network topologies. In particular, we obtain near-optimal routing time for the tree. mesh, butterfly, and hypercube. 2. Complexity. By a reduction from Vertex Coloring, we show that optimal Direct Routing is inapproximable, unless P = NP. 3. Lower Bounds for Buffering. We show that certain direct routing problems cannot be solved efficiently | en |
dc.description.abstract | in order to solve these problems, any routing algorithm needs buffers. We give non-trivial lower bounds on such buffering requirements for general routing algorithms. © 2006 Springer Science+Business Media, Inc. | en |
dc.source | Algorithmica (New York) | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-33646417082&doi=10.1007%2fs00453-005-1189-3&partnerID=40&md5=b94b2a059259db47586bbf4bc2f6e53c | |
dc.subject | Algorithms | en |
dc.subject | Topology | en |
dc.subject | Computational complexity | en |
dc.subject | Polynomials | en |
dc.subject | Packet networks | en |
dc.subject | Congestion | en |
dc.subject | Routers | en |
dc.subject | Dilation | en |
dc.subject | Bufferless routing | en |
dc.subject | Communication algorithms | en |
dc.subject | Direct routing | en |
dc.title | Direct routing: Algorithms and complexity | en |
dc.type | info:eu-repo/semantics/article | |
dc.identifier.doi | 10.1007/s00453-005-1189-3 | |
dc.description.volume | 45 | |
dc.description.issue | 1 | |
dc.description.startingpage | 45 | |
dc.description.endingpage | 68 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :11</p> | en |
dc.source.abbreviation | Algorithmica (New York) | en |
dc.contributor.orcid | Busch, Costas [0000-0002-4381-4333] | |
dc.contributor.orcid | Spirakis, Paul G. [0000-0001-5396-3749] | |
dc.gnosis.orcid | 0000-0002-4381-4333 | |
dc.gnosis.orcid | 0000-0001-5396-3749 | |