Scholarlink

Given a directed graph, we present and experimentally validate new heuristics to find good linear orderings of its vertices so to obtain Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. We will also show that, in many cases, the newly proposed linear orderings along with an improved heuristic algorithm to reinsert eliminated arcs, which has a good polynomial upper bounds, produce, in fact, a minimum FAS.

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

Efficient Vertex Linear Orderings to Find Minimal Feedback Arc Sets (minFAS)

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Claudia Cavallaro,
  • Vincenzo Cutello,
  • Mario Pavone

摘要

Given a directed graph, we present and experimentally validate new heuristics to find good linear orderings of its vertices so to obtain Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. We will also show that, in many cases, the newly proposed linear orderings along with an improved heuristic algorithm to reinsert eliminated arcs, which has a good polynomial upper bounds, produce, in fact, a minimum FAS.