New results on routing via matchings on graphs

DOI10.1007/978-3-662-55751-8_7MaRDI QIDQ1679957zbMATH OpenOpenAlexFDO

Authors Indranil Banerjee, Dana Richards

Publication date 22 November 2017

Full work available at URL https://arxiv.org/abs/1706.09355

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper we present some new complexity results on the routing time of a graph under the extit{routing via matching} model. This is a parallel routing model which was introduced by Alon et alcite{alon1994routing}. 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,\mathrm{...},n$ and the destination vertices of the pebbles are given by a permutation $pi$. The problem is to find a minimum step routing scheme for the input permutation $pi$. This is denoted as the routing time $rt(G,pi)$ of $G$ given $pi$. 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.

Recommendations

• Routing Permutations on Graphs via Matchings
• Routing permutations on graphs via factors
• Optimal Bounds for Matching Routing on Trees
• The time complexity of permutation routing via matching, token swapping and a variant
• scientific article; zbMATH DE number 1202980

Cited in

(11)

• New inequalities for the general routing problem
• scientific article; zbMATH DE number 1202980 (Why is no real title available?)
• Routing Permutations on Graphs via Matchings
• The time complexity of permutation routing via matching, token swapping and a variant
• scientific article; zbMATH DE number 7559364 (Why is no real title available?)
• A new approach for routing in arrangement graphs and its performance evaluation
• Routing permutations on spectral expanders via matchings
• New results in graph routing
• Hardness of token swapping on trees
• Coordinated motion planning: multi-agent path finding in a densely packed, bounded domain
• Improved hardness-of-approximation for token-swapping

This page was built for publication: New results on routing via matchings on graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1679957)