学术时间轴

Hardness and Algorithms for Packing Steiner Trees in Digraphs

Abstract
Packing combinatorial objects—such as graphs, digraphs, and hypergraphs—by smaller ones is one of the central problems in graph theory and combinatorial optimization. Among these, the Steiner tree packing problem stands out not only for its theoretical significance but also for its practical relevance, particularly in VLSI circuit design. Over the past decades, it has attracted much attention from researchers across graph theory, combinatorial optimization, and theoretical computer science, and has matured into a well-established area. In this talk, we survey known hardness and algorithmic results for the directed Steiner tree packing problem, along with several related topics. This presentation is based on joint work with Anders Yeo, Shanshan Yu, and Xiaoyan Zhang.