Scholarlink

<p>We present a counterexample to the order relation between the largest common subtree and the smallest common supertree as claimed by Rosselló and Valiente (Theor Comput Sci 362(1–3):33–53, 2006). Furthermore, we demonstrate that knowing the solution to one of these problems does not substantially simplify the computation of the other; solving the second problem still requires processing information linear in the size of the original trees.</p>

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

A Counterexample to the Order Relation Between Largest Common Subtree and Smallest Common Supertree

  • 期刊论文

  • 发表日期：

    2026年1月14日

查看全文
  • Maciej Brzeski

摘要

We present a counterexample to the order relation between the largest common subtree and the smallest common supertree as claimed by Rosselló and Valiente (Theor Comput Sci 362(1–3):33–53, 2006). Furthermore, we demonstrate that knowing the solution to one of these problems does not substantially simplify the computation of the other; solving the second problem still requires processing information linear in the size of the original trees.