首页    期刊浏览 2024年11月05日 星期二
登录注册

文章基本信息

  • 标题:A Linear Kernel for Finding Square Roots of Almost Planar Graphs
  • 本地全文:下载
  • 作者:Petr A. Golovach ; Dieter Kratsch ; Dani{\"e}l Paulusma
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2016
  • 卷号:53
  • 页码:4:1-4:14
  • DOI:10.4230/LIPIcs.SWAT.2016.4
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph is a graph that can be made planar by the removal of at most k vertices. We prove that the generalization of Square Root, in which we are given two subsets of edges prescribed to be in or out of a square root, respectively, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.
  • 关键词:planar graphs; square roots; linear kernel
国家哲学社会科学文献中心版权所有