...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>LIPIcs : Leibniz International Proceedings in Informatics >Efficient and Adaptive Parameterized Algorithms on Modular Decompositions
【24h】

Efficient and Adaptive Parameterized Algorithms on Modular Decompositions

机译：模块化分解的高效自适应参数化算法

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study the influence of a graph parameter called modular-width on the time complexity for optimally solving well-known polynomial problems such as Maximum Matching, Triangle Counting, and Maximum s-t Vertex-Capacitated Flow. The modular-width of a graph depends on its (unique) modular decomposition tree, and can be computed in linear time O(n+m) for graphs with n vertices and m edges. Modular decompositions are an important tool for graph algorithms, e.g., for linear-time recognition of certain graph classes.Throughout, we obtain efficient parameterized algorithms of running times O(f(mw)n+m), O(n+f(mw)m) , or O(f(mw)+n+m) for low polynomial functions f and graphs of modular-width mw. Our algorithm for Maximum Matching, running in time O(mw^2 log mw n+m), is both faster and simpler than the recent O(mw^4n+m) time algorithm of Coudert et al. (SODA 2018). For several other problems, e.g., Triangle Counting and Maximum b-Matching, we give adaptive algorithms, meaning that their running times match the best unparameterized algorithms for worst-case modular-width of mw=Theta(n) and they outperform them already for mw=o(n), until reaching linear time for mw=O(1).
机译：我们研究了一种称为模数宽度的图形参数对时间复杂度的影响，以最佳地解决众所周知的多项式问题，例如最大匹配，三角形计数和最大s-t顶点容量流。图的模宽取决于其（唯一）模分解树，对于具有n个顶点和m个边的图，可以在线性时间O（n + m）中计算。模块化分解是用于图算法的重要工具，例如用于某些图类的线性时间识别。贯穿全文，我们获得了运行时间O（f（mw）n + m），O（n + f（mw）的有效参数化算法）m）或O（f（mw）+ n + m）用于低多项式函数f和模宽度mw的图。我们的最大匹配算法在时间O（mw ^ 2 log mw n + m）上运行，比最近的Coudert等人的O（mw ^ 4n + m）时间算法更快，更简单。 （SODA 2018）。对于其他一些问题，例如“三角形计数”和“最大b匹配”，我们给出了自适应算法，这意味着对于mw = Theta（n）的最坏情况模块化宽度，它们的运行时间与最佳非参数化算法匹配，并且它们在性能上已经超过了它们mw = o（n），直到达到mw = O（1）的线性时间为止。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号