[合集] 这个图问题的复杂度是多少？# Programming - 葵花宝典
b*y
1 楼
☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Mon Mar 10 20:19:59 2008) 提到:
给定一个n顶点的无向图。
把这n个点放在一维数轴上1到n的n个整点位置上去
每个整点只能有一个顶点。
要求一个放置方式，使得，所有的边的长度总和最小
边的长度，定义为顶点之间的位置距离。
☆─────────────────────────────────────☆
pptwo (pp) 于 (Mon Mar 10 21:22:01 2008) 提到:
NP hard把，我记得，你要解多大规模的问题？
paper很多，随便找了一个
☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Mon Mar 10 21:42:36 2008) 提到:
100个点。
如果图是planar的，应该会有很大帮助？
☆─────────────────────────────────────☆
pptwo (pp) 于
kukutf (五脚蟹★酷酷豆腐) 于 (Mon Mar 10 20:19:59 2008) 提到:
给定一个n顶点的无向图。
把这n个点放在一维数轴上1到n的n个整点位置上去
每个整点只能有一个顶点。
要求一个放置方式，使得，所有的边的长度总和最小
边的长度，定义为顶点之间的位置距离。
☆─────────────────────────────────────☆
pptwo (pp) 于 (Mon Mar 10 21:22:01 2008) 提到:
NP hard把，我记得，你要解多大规模的问题？
paper很多，随便找了一个
☆─────────────────────────────────────☆
kukutf (五脚蟹★酷酷豆腐) 于 (Mon Mar 10 21:42:36 2008) 提到:
100个点。
如果图是planar的，应该会有很大帮助？
☆─────────────────────────────────────☆
pptwo (pp) 于