...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Solving Problems on Graphs of High Rank-Width
【24h】

Solving Problems on Graphs of High Rank-Width

机译：高秩宽图的求解问题

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

A modulator in a graph is a vertex set whose deletion places the considered graph into some specified graph class. The cardinality of a modulator to various graph classes has long been used as a structural parameter which can be exploited to obtain fixed-parameter algorithms for a range of hard problems. Here we investigate what happens when a graph contains a modulator which is large but "well-structured" (in the sense of having bounded rank-width). Can such modulators still be exploited to obtain efficient algorithms? And is it even possible to find such modulators efficiently? We first show that the parameters derived from such well-structured modulators are more powerful for fixed-parameter algorithms than the cardinality of modulators and rank-width itself. Then, we develop a fixed-parameter algorithm for finding such well-structured modulators to every graph class which can be characterized by a finite set of forbidden induced subgraphs. We proceed by showing how well-structured modulators can be used to obtain efficient parameterized algorithms for Minimum Vertex Cover and Maximum Clique. Finally, we use the concept of well-structured modulators to develop an algorithmic meta-theorem for deciding problems expressible in monadic second order logic, and prove that this result is tight in the sense that it cannot be generalized to LinEMSO problems.
机译：图中的调制器是一个顶点集，其删除将考虑的图置于指定的图类中。长期以来，调制器对各种图形类别的基数一直被用作结构参数，可以利用该结构参数来获得针对一系列难题的固定参数算法。在这里，我们研究当图形包含一个较大但“结构良好”的调制器时（在具有限定的秩宽度的意义上），会发生什么情况。这样的调制器是否仍然可以用来获得有效的算法？甚至有可能有效地找到这种调制器吗？我们首先表明，从结构良好的调制器派生的参数对于固定参数算法比调制器的基数和秩宽度本身更强大。然后，我们开发了一种固定参数算法，用于为每个图类找到结构良好的调制器，这些图类可以通过有限的一组禁止诱导子图来表征。我们通过展示结构良好的调制器如何用于获得有效的参数化算法来实现“最小顶点覆盖”和“最大派系”来进行研究。最后，我们使用结构良好的调制器的概念来开发算法元定理，以决定一元二阶逻辑可表达的问题，并证明该结果是严格的，因为它不能推广到LinEMSO问题。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号