[转载] 我也问一道题 - CS版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

CS版 - [转载] 我也问一道题

相关主题
● 问一个feedback vertex set的问题	● [求]建议：初次与潜在老板谈话。
● 牛人来综述一下BN和MN有什么区别?	● Ask one algorithm question
● 关于有向图的 subgraph mining~~~	● Mapquest面试题，大伙儿看看
● 问大家一个有向图的问题	● 问一个关于minimum spanning tree的问题
● 请教minimum set cover Problem	● 算法问题
● 问一个NPC 的问题	● 哪里可以看到 #P-complete 问题的列表？
● 问个图的算法	● 很严肃的想讨论一下未来出路问题
● 问个算法问题	● CRA的CIFellows Projects申请人的数据出来了

相关话题的讨论汇总
话题: 问一话题: 道题话题: steiner话题: 给定话题: 集合

进入CS版参与讨论

(共1页)

s***e
发帖数: 2

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

y***s
发帖数: 294

see USTC

【在 s***e 的大作中提到】

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

(共1页)

进入CS版参与讨论

相关主题
● CRA的CIFellows Projects申请人的数据出来了	● 请教minimum set cover Problem
● Conference: I-SPAN	● 问一个NPC 的问题
● 请教背包问题。	● 问个图的算法
● 算法好难阿，书能看懂，可是题都不会做	● 问个算法问题
● 问一个feedback vertex set的问题	● [求]建议：初次与潜在老板谈话。
● 牛人来综述一下BN和MN有什么区别?	● Ask one algorithm question
● 关于有向图的 subgraph mining~~~	● Mapquest面试题，大伙儿看看
● 问大家一个有向图的问题	● 问一个关于minimum spanning tree的问题

相关话题的讨论汇总
话题: 问一话题: 道题话题: steiner话题: 给定话题: 集合

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天