On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology
On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology
复制标题
完整多部分图中的在线最大匹配及其对星形拓扑上最小 ADM 问题的影响
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Zaks
中科院分区：
文献类型：
--
作者：
Mordechai Shalom;Prudence W. H. Wong;S. Zaks
光网络中的基本问题之一是将波长分配给给定的一组光路（即，着色），以最小化ADM开关的数量。在本文中，我们提出了完整多部分图中的最大匹配与星形网络中的 ADM 最小化之间的联系。寻找最大匹配的严格 2/3 竞争比意味着寻找最小化 ADM 数量的着色的严格 10/9 竞争比。
One of the basic problems in optical networks is assigning wavelengths to (namely, coloring of) a given set of lightpaths so as to minimize the number of ADM switches. In this paper we present a connection between maximum matching in complete multipartite graphs and ADM minimization in star networks. A tight 2/3 competitive ratio for finding a maximum matching implies a tight 10/9 competitive ratio for finding a coloring that minimizes the number of ADMs.