New Results on Routing via Matchings on Graphs
Abstract
In this paper we present some new complexity results on the routing time of a graph under the routing via matching model. This is a parallel routing model which was introduced by Alon et al. [1]. The model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data (pebbles) with its matched partner. Let G be a connected graph with vertices labeled from {1, …, n} and the destination vertices of the pebbles are given by a permutation π. The problem is to find a minimum step routing scheme for the input permutation π. This is denoted as the routing time rt(G, π) of G given π. In this paper we characterize the complexity of some known problems under the routing via matching model and discuss their relationship to graph connectivity and clique number. We also introduce some new problems in this domain, which may be of independent interest.
Recommended Citation
A. Banerjee and D. Richards, "New Results on Routing via Matchings on Graphs," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10472 LNCS, pp. 69 - 81, Springer Verlag, Sep 2017.
The definitive version is available at https://doi.org/10.1007/978-3-662-55751-8_7
Meeting Name
21st International Symposium on Fundamentals of Computation Theory, FCT 2017 (2017: Sep. 11-13, Bordeaux, France)
Department(s)
Computer Science
Keywords and Phrases
Complex Networks; Computation Theory, Communication Schemes; Complexity Results; Connected Graph; Distributed Networks; Graph Connectivity; Matching Models; Parallel Routing; Routing Scheme, Graph Theory
International Standard Book Number (ISBN)
978-366255750-1
International Standard Serial Number (ISSN)
0302-9743
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2017 Springer Verlag, All rights reserved.
Publication Date
13 Sep 2017
Comments
Published as Indranil Banerjee.