On-line maximum matching in complete multi-partite graphs with an application to optical networks
On-line maximum matching in complete multi-partite graphs with an application to optical networks
复制标题
完整多部分图中的在线最大匹配及其在光网络中的应用
DOI：
10.1016/j.dam.2014.10.040
复制
发表时间：
2016
影响因子：
1.1
通讯作者：
Shalom M
中科院分区：
文献类型：
--
作者：
Shalom M
求图中的最大匹配是一个经典问题。该问题的在线版本（图的顶点和/或边一次给出一个，并且算法必须增量计算匹配）已经研究了二十多年。文献中考虑了这个问题的许多变体。开创性的工作（Karp, 1990）考虑了一个二部图，其中一个部分的顶点与它们的关联边一次显示一个。在本文中，我们考虑了极大的d-可色图，它就是完全的d-部图。顶点与它们的相关边一起一次到达一个，或者等价地在图的某个给定的d-着色中与它们相应的颜色一起到达。针对这一在线问题，我们提出了一个2/3竞争的最优确定性算法。该问题与星形拓扑光网络中线路终端成本最小化问题密切相关。我们考虑光路以在线方式到达给定的恒星网络。我们的结果暗示了一种紧密的10/9竞争算法，用于在这样的网络中寻找最小化线路终端成本的波长分配。
Finding a maximum matching in a graph is a classical problem. The on-line versions of the problem in which the vertices and/or edges of the graph are given one at a time and an algorithm has to calculate a matching incrementally have been studied for more than two decades. Many variants of the problem are considered in the literature. The pioneering work (Karp, 1990) considers a bipartite graph where the vertices of one part are revealed one at a time together with their incident edges. In this work we consider maximal d-colorable graphs which are exactly the complete d-partite graphs. The vertices arrive one at a time together with their incident edges, or equivalently with their corresponding colors in some given d-coloring of the graph. We present an optimal 2/3-competitive deterministic algorithm for this on-line problem. This problem is closely related to that of minimizing the cost of line terminals in star topology optical network. We consider lightpaths arriving in an on-line fashion on a given star network. Our result implies a tight 10/9-competitive algorithm for finding a wavelength assignment minimizing the cost of line terminals in such a network.
登录
查看更多内容
重新审视环形网络中 SONET ADM 的最小化
影响因子：
3.7
作者：
L. Epstein;Asaf Levin;Betzalel Menahem
通讯作者：
Betzalel Menahem
完整多部分图中的在线最大匹配及其对星形拓扑上最小 ADM 问题的影响
DOI：
--
发表时间：
2009
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
Mordechai Shalom;Prudence W. H. Wong;S. Zaks
通讯作者：
S. Zaks
最小化电子线路终端以实现一般 WDM 光网络中的自动环保护
DOI：
--
发表时间：
2002
期刊：
IEEE J. Sel. Areas Commun.
影响因子：
--
作者：
G. Călinescu;O. Frieder;P. Wan
通讯作者：
P. Wan
最小化 WDM 定向光纤树上的 ADM
DOI：
--
发表时间：
2003
期刊：
Journal of Computational Science and Technology
影响因子：
--
作者：
F. Zhou;Guoliang Chen;Yinlong Xu;J. Gu
通讯作者：
J. Gu
最优节点路由
DOI：
--
发表时间：
2006
期刊：
Symposium on Theoretical Aspects of Computer Science
影响因子：
--
作者：
Y. Azar;Yoel Chaiutin
通讯作者：
Yoel Chaiutin