[转载] 我也问一道题# Engineering - 工程
j*l
1 楼
【 以下文字转载自 USTC 讨论区 】
【 原文由 jollyl 所发表 】
我不知道下面的问题的难度如何，是不是某种NP的？
给定有向图，一个点s和若干点的集合D，要求判断有向steiner树的存在性。
一个约束是对每个点v，都规定了其孩子集合的所有可能，在steiner树中的
孩子集合必须是给定的若干可能中的一个。
我只知道，如果对无向图，当D包含剩下所有点，任意不超过k个孩子都允许，
问题称为degree limited spanning tree，是NPC
对我的这个问题，有没有高手知道答案？
【 原文由 jollyl 所发表 】
我不知道下面的问题的难度如何，是不是某种NP的？
给定有向图，一个点s和若干点的集合D，要求判断有向steiner树的存在性。
一个约束是对每个点v，都规定了其孩子集合的所有可能，在steiner树中的
孩子集合必须是给定的若干可能中的一个。
我只知道，如果对无向图，当D包含剩下所有点，任意不超过k个孩子都允许，
问题称为degree limited spanning tree，是NPC
对我的这个问题，有没有高手知道答案？