| 查看: 1095 | 回复: 15 | ||
| 当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖 | ||
[求助]
万能的小木虫，帮帮我吧， 一个类似 terminal Steiner tree problem问题
|
||
|
有一个无向图G(v,e),假设有V有100个顶点。 我现在给定一个n,比如10， 那么，以叶子节点建立一个子图，子图是以V中任意n个叶子连接建立的最小生成树。 请问建立这个最小生成树问题是不是一个NP hard问题，有没有相关的NP问题，用以证明。 查了些文献，似乎是一个 terminal Steiner tree problem，但区别是那个顶点的子集是给定的，而我这个问题只是确定数量。这个更不一定，是不是可以这样说，他那个是np, 我这个就更是np了，假如叶子有m个点，就是多了Cm,n倍而已。 [ Last edited by zhangwzh on 2012-7-25 at 10:54 ] |
回复此楼» 猜你喜欢
真诚求助：手里的省社科项目结项要求主持人一篇中文核心，有什么渠道能发核心吗
已经有8人回复
-
寻求一种能扛住强氧化性腐蚀性的容器密封件
已经有5人回复
-
论文投稿，期刊推荐
已经有6人回复
-
请问哪里可以有青B申请的本子可以借鉴一下。
已经有4人回复
-
孩子确诊有中度注意力缺陷
已经有14人回复
-
请问下大家为什么这个铃木偶联几乎不反应呢
已经有5人回复
-
请问有评职称，把科研教学业绩算分排序的高校吗
已经有5人回复
-
2025冷门绝学什么时候出结果
已经有3人回复
-
天津工业大学郑柳春团队欢迎化学化工、高分子化学或有机合成方向的博士生和硕士生加入
已经有4人回复
-
康复大学泰山学者周祺惠团队招收博士研究生
已经有6人回复
5楼2012-08-10 12:13:11
dybo
木虫 (正式写手)
- 应助: 8 (幼儿园)
- 金币: 5500.2
- 散金: 134
- 红花: 43
- 帖子: 625
- 在线: 239.9小时
- 虫号: 897154
- 注册: 2009-11-08
- 性别: GG
- 专业: 草地科学
2楼2012-08-10 12:04:38
3楼2012-08-10 12:10:49
4楼2012-08-10 12:11:26