On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology

机译：完整多部分图中的在线最大匹配，这对星形拓扑中的最小ADM问题有影响

获取原文

页面导航

摘要
著录项
相似文献
相关主题

摘要

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.

机译：光网络中的基本问题之一是将波长分配给给定的一组光路（即，对它们进行着色），以最大程度地减少ADM开关的数量。在本文中，我们提出了完整多部分图中的最大匹配与星形网络中的ADM最小化之间的联系。严格的2/3竞争比率（用于找到最大的匹配项）意味着严格的10/9竞争比率（用于查找使ADM数量最少的着色）。

著录项

来源
《Structural information and communication complexity》|2010年|P.281-294|共14页
会议地点
作者
Mordechai Shalom; Prudence W.H. Wong; Shmuel Zaks;
展开▼
作者单位

展开▼
会议组织
原文格式 PDF
正文语种
中图分类信息处理（信息加工）;
关键词
online matching; multi-partite graphs; wavelength as-signment; wavelength division multiplexing (WDM); optical networks; add-drop multiplexer (ADM);

机译：在线匹配;多部分图波长分配波分复用（WDM）;光网络;分插复用器（ADM）;
入库时间 2022-08-26 15:01:59

相似文献

外文文献
中文文献
专利

1. On-line maximum matching in complete multi-partite graphs with an application to optical networks [J] . Shalom Mordechai, Wong Prudence W. H., Zaks Shmuel Discrete Applied Mathematics . 2016,第Null期

机译：完整的多部分图中的在线最大匹配及其在光网络中的应用
2. Extremal Matching Energy and the Largest Matching Root of Complete Multipartite Graphs [J] . Xiaolin Chen, Huishu Lian Complexity . 2019,第1期

机译：极值匹配能量和完整多党图的最大匹配根
3. Minimum Number of Vertices of Graphs without Perfect Matching, with Given Edge Connectivity and Minimum and Maximum Degrees [J] . Indriati Nurul Hidayah, Purwanto The Journal of Combinatorial Mathematics and Combinatorial Computing . 2014,第feba期

机译：在给定的边缘连通性以及最小和最大程度的情况下，没有完美匹配的图的顶点的最小数量
4. On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology [C] . Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks International Colloquium on Structural Information and Communication Complexity . 2010

机译：在线在完整的多私人图中的在线最大匹配，并对星形拓扑的最低adm问题影响
5. Using a maximum matching to find a minimum vertex cover in a graph. [D] . Shu, Jung-huei. 1998

机译：使用最大匹配来找到图形中的最小顶点覆盖。
6. Eigenvalues of the resistance-distance matrix of complete multipartite graphs [O] . Kinkar Chandra Das, Yujun Yang -1

机译：完整多部分图的电阻距离矩阵的特征值
7. On-line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology [O] . Mordechai Shalom, Prudence W. H. Wong, Shmuel Zaks 2010

机译：完整多部分图中的在线最大匹配，这对星形拓扑中的最小ADM问题有影响

On-Line Maximum Matching in Complete Multipartite Graphs with Implications to the Minimum ADM Problem on a Star Topology

摘要

著录项

相似文献

相关主题

期刊订阅