论文标题
遍布叶子的叶子
Leafy Spanning Arborescences in DAGs
论文作者
论文摘要
在计算机网络中广播是一种同时将消息传输给所有收件人的方法。在这种情况下，通常使用带有许多叶子的树来执行广播很常见，因为内部节点必须转发收到的消息，而叶子只是受体。我们考虑了一个有向图〜$ d $的次要问题，如果存在，则发现D的跨度d（如果存在），则叶子数量最多。在本文中，我们专注于根生根的无环形图，为此，该问题已知是maxsnp-hard。以前在此类的有向图上以此问题而闻名2个附属物。我们对此结果进行了改进，并提出了（3/2） - approximation。我们还适应了无方案的结果，并为根系有向无环图上的最大叶片跨度树脂的顶点加权版本得出了不合适的结果。
Broadcasting in a computer network is a method of transferring a message to all recipients simultaneously. It is common in this situation to use a tree with many leaves to perform the broadcast, as internal nodes have to forward the messages received, while leaves are only receptors. We consider the subjacent problem of, given a directed graph~$D$, finding a spanning arborescence of D, if one exists, with the maximum number of leaves. In this paper, we concentrate on the class of rooted directed acyclic graphs, for which the problem is known to be MaxSNP-hard. A 2-approximation was previously known for this problem on this class of directed graphs. We improve on this result, presenting a (3/2)-approximation. We also adapt a result for the undirected case and derive an inapproximability result for the vertex-weighted version of Maximum Leaf Spanning Arborescence on rooted directed acyclic graphs.
