Scholarlink

<p>We present a simple linear-time algorithm that finds a spanning tree <i>T</i> of a given 2-edge-connected graph <i>G</i> such that each vertex <i>v</i> of <i>T</i> has degree at most <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\lceil \frac{\deg _G(v)}{2}\rceil + 1\)</EquationSource> </InlineEquation>.</p>

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

Low-degree spanning trees of 2-edge-connected graphs in linear time

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年10月25日

查看全文
  • Dariusz Dereniowski,
  • Janusz Dybizbański,
  • Przemysław Karpiński,
  • Michał Zakrzewski,
  • Paweł Żyliński

摘要

We present a simple linear-time algorithm that finds a spanning tree T of a given 2-edge-connected graph G such that each vertex v of T has degree at most \(\lceil \frac{\deg _G(v)}{2}\rceil + 1\) .