Optimal Bounds for Matching Routing on Trees

DOI10.1137/S0895480197323159MaRDI QIDQ4255808zbMATH OpenFDO

Authors Louxin Zhang

Publication date 27 June 1999

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480197323159

zbMATH Keywords

matching routingoff-line algorithmstrees

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Routing on trees via matchings
• Routing on trees
• On-line matching routing on trees
• ON THE ROUTING NUMBER OF COMPLETE d-ARY TREES

Cited in

(23)

• On the complexity of an optimal routing tree problem
• Many-to-many routing on trees via matchings
• On-line matching routing on trees
• New results on routing via matchings on graphs
• Shortest augmenting paths for online matchings on trees
• Waypoint routing on bounded treewidth graphs
• Collision-free network exploration
• Routeing on trees
• scientific article; zbMATH DE number 1202980 (Why is no real title available?)
• scientific article; zbMATH DE number 1303574 (Why is no real title available?)
• The time complexity of permutation routing via matching, token swapping and a variant
• scientific article; zbMATH DE number 2086374 (Why is no real title available?)
• Routing on trees via matchings
• scientific article; zbMATH DE number 7559364 (Why is no real title available?)
• ON THE ROUTING NUMBER OF COMPLETE d-ARY TREES
• scientific article; zbMATH DE number 2188361 (Why is no real title available?)
• Routing permutations on spectral expanders via matchings
• Dynamic tree routing under the “matching with consumption” model
• A unified framework for the expander mixing lemma for irregular graphs and its applications
• Parallel token swapping for qubit routing
• Hardness of token swapping on trees
• Extremal permutations in routing cycles
• Improved hardness-of-approximation for token-swapping

This page was built for publication: Optimal Bounds for Matching Routing on Trees

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