.png){kind=icon}
返回
Structural Parameterization of Steiner Tree Packing
.png){kind=icon}
PRE
AI
DOI：10.4230/LIPIcs.STACS.2026.51.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
STEINER树包装（STP）是经典复杂性理论中一个臭名昭著的难题，对VLSI电路设计具有实际相关性。先前的研究通过提供启发式或近似算法来处理此问题。在本文中，我们展示了针对以输入图的结构参数为参数的STP的第一批FPT算法。具体而言，我们证明了STP是可固定参数处理的，其参数为输入图的树割宽度以及断裂数。为了实现我们的结果，我们将EDGE- DISJOINT PATHS（EDP）的技术推广到GENERALIZED STEINER TREE PACKING（GSTP），后者概括了STP和EDP。首先，我们推导出GSTP的增广图的概念，类似于EDP。然后我们证明GSTP是FPT，其参数为增广图的树割宽度、增广图的断裂数以及输入图的瘦树割宽度。后两个结果先前已知适用于EDP；我们的结果将这些推广到GSTP，并改进了断裂数参数的运行时间。另一方面，尽管对问题的结构复杂性进行了广泛研究，但EDP是否以增广图的树割宽度为参数可固定参数处理仍是一个悬而未决的问题。我们对此问题给出了肯定的答复。
Keyword:
Steiner tree packing
structural parameters
fixed-parameter tractability
期刊
机构
引用论文
暂无论文信息