代码之家 › 专栏 › 技术社区 › Keith Pham

最大化给定预算的子图“价值”

approximation graph-theory graph algorithm

Keith Pham · 技术社区 · 8 年前

我想解决的场景是最大化问题,其中连接的无向图中的每个顶点都有一个价值费用

给定起始顶点和 成本预算 价值 (包括起始顶点)?

1 回复 | 直到 8 年前

Peter de Rivaz 8 年前

Steiner tree problem in graphs 通过将每个端子的值设置为1,每个顶点的成本为0,每个边的成本为1。当且仅当成本预算为k的算法能够从所有终端捕获值时,才存在权重为k的斯坦纳树。

这可能有助于研究斯坦纳树的文献,以获得近似解的一些想法。

推荐文章

Rosie Lomas · 在ggplot中设置数字刻度

3 年前

Mahin Rahman · 我的培训和测试图表保持不变,有人能帮我解释一下,或者解释一下我哪里出错了?

4 年前

nedlaback · 在O(V+E)图中寻找瓶颈边

8 年前

Skampak · R visNetwork:创建新类型的边

8 年前

Habil Ganbarli · 在完整图上进行MST聚类(用于余弦相似性)

8 年前

Vaibhav · 在r Shinny中的Visnetwork中撤消单击事件

8 年前

Anuja · 长度l在R中的最短路径

8 年前

Cbhihe · 优化Neo4j查询,有条件地创建新关系

8 年前

fghjk · 绘制轨迹(python)

8 年前

LBerger · 计算图形图像中的名称使用(TensorBoard)

8 年前