首页    期刊浏览 2025年06月05日 星期四
登录注册

文章基本信息

  • 标题:Metatheorems for Dynamic Weighted Matching
  • 本地全文:下载
  • 作者:Daniel Stubbs ; Virginia Vassilevska Williams
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2017
  • 卷号:67
  • 页码:58:1-58:14
  • DOI:10.4230/LIPIcs.ITCS.2017.58
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We consider the maximum weight matching (MWM) problem in dynamic graphs. We provide two reductions. The first reduces the dynamic MWM problem on m-edge, n-node graphs with weights bounded by N to the problem with weights bounded by (n/eps)^2, so that if the MWM problem can be alpha-approximated with update time t(m,n,N), then it can also be (1+eps)alpha-approximated with update time O(t(m,n,(n/eps)^2)log^2 n+log n loglog N)). The second reduction reduces the dynamic MWM problem to the dynamic maximum cardinality matching (MCM) problem in which the graph is unweighted. This reduction shows that if there is an \alpha-approximation algorithm for MCM with update time t(m,n) in m-edge n-node graphs, then there is also a (2+eps)alpha-approximation algorithm for MWM with update time O(t(m,n)eps^{-2}log^2 N). We also obtain better bounds in our reductions if the ratio between the largest and the smallest edge weight is small. Combined with recent work on MCM, these two reductions substantially improve upon the state-of-the-art of dynamic MWM algorithms.
  • 关键词:dynamic algorithms; maximum matching; maximum weight matching
国家哲学社会科学文献中心版权所有