Scholarlink

<p>The diameter of a directed graph is the maximum distance between any pair of vertices. We study a problem that generalizes <span>Oriented Diameter</span>: For a given directed graph and a positive integer <i>d</i>, what is the minimum number of arc reversals required to obtain a graph with diameter at most <i>d</i>? We investigate variants of this problem, considering the number of arc reversals and the target diameter as parameters. We show hardness results under certain parameter restrictions, and give polynomial time algorithms for planar and cactus graphs. This work is partly motivated by the relation between oriented diameter and the volume of directed edge polytopes, which we show to be independent.</p>

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

Diameter Reduction via Arc Reversal

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2025年11月12日

查看全文
  • Panna Gehér,
  • Max Kölbl,
  • Mirabel Mendoza-Cadena,
  • Daniel P. Szabo

摘要

The diameter of a directed graph is the maximum distance between any pair of vertices. We study a problem that generalizes Oriented Diameter: For a given directed graph and a positive integer d, what is the minimum number of arc reversals required to obtain a graph with diameter at most d? We investigate variants of this problem, considering the number of arc reversals and the target diameter as parameters. We show hardness results under certain parameter restrictions, and give polynomial time algorithms for planar and cactus graphs. This work is partly motivated by the relation between oriented diameter and the volume of directed edge polytopes, which we show to be independent.