Scholarlink

<p>In the <span>3-Leaf Power Vertex Deletion</span> (resp., <span>3-Leaf Power Edge Deletion</span>) problem, the input is a graph <i>G</i> and an integer <i>k</i>, and the goal is to decide whether there is a set of at most <i>k</i> vertices (resp., edges) whose removal from <i>G</i> results in a graph that is a 3-leaf power. In this paper we give <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O^*(4.237^k)\)</EquationSource> </InlineEquation>-time algorithms for <span>3-Leaf Power Vertex Deletion</span> and <span>3-Leaf Power Edge Deletion</span>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Faster algorithms for 3-leaf power modification problems

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年12月5日

查看全文
  • Dekel Tsur

摘要

In the 3-Leaf Power Vertex Deletion (resp., 3-Leaf Power Edge Deletion) problem, the input is a graph G and an integer k, and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph that is a 3-leaf power. In this paper we give \(O^*(4.237^k)\) -time algorithms for 3-Leaf Power Vertex Deletion and 3-Leaf Power Edge Deletion.