On-line maximum matching in complete multi-partite graphs with an application to optical networks

DOI10.1016/j.dam.2014.10.040zbMath1326.05124OpenAlexW1980531533MaRDI QIDQ896661

Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks

Publication date: 10 December 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.10.040

zbMATH Keywords

maximum matchingon-line algorithmsoptical networksswitching costmulti-partite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal on-line colorings for minimizing the number of ADMs in optical networks
• Matching theory
• Traffic partition in WDM/SONET rings to minimize SONET ADMs
• Minimizing ADMs on WDM directed fiber trees
• Minimization of SONET ADMs in ring networks revisited
• On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology
• Online Weighted Matching
• Optimal Node Routing
• Management of multi-queue switches in QoS networks

This page was built for publication: On-line maximum matching in complete multi-partite graphs with an application to optical networks