问一个feedback vertex set的问题 - CS版

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

CS版 - 问一个feedback vertex set的问题

相关主题
● 问个在图中删除边和点的算法问题 (转载)	● google maps 的data structure 是什么？
● [转载] 我也问一道题	● Valgrind报uninitialized value was created by a heap allocat (转载)
● 牛人来综述一下BN和MN有什么区别?	● [转载] 有搞算法的大侠吗？？？？？问个问题！！！
● 关于有向图的 subgraph mining~~~	● 帮忙找一篇paper
● 问大家一个有向图的问题	● 请教minimum set cover Problem
● 说说做系统的经验吧	● max independent set
● some questions about the geometry	● Re: Efficient duplicate filtering for st
● 请问哪儿有现成的minimum vertex cover code	● Theory的高手们指教一下吧

相关话题的讨论汇总
话题: vertex话题: 有向图话题: algorithm话题: feedback话题: set

进入CS版参与讨论

(共1页)

d**k
发帖数: 114

我们知道minimum feedback vertex set problem是在一个有向图中去掉最少的点
使得剩下的图是无环有向图。这个问题是NP的，但是有现成的approximation algorithm
。
我现在的问题是：给出两个有向图，这两个图中的点一一对应。现在要去掉最少的点，
使得这两个图都变成无环有向图。
请问有没有对这样的问题的定义和现成的算法？

x*b
发帖数: 253

algorithm
u can easily extend the approximation algorithm to get an algorithm for 2
graphs.

【在 d**k 的大作中提到】

: 我们知道minimum feedback vertex set problem是在一个有向图中去掉最少的点
: 使得剩下的图是无环有向图。这个问题是NP的，但是有现成的approximation algorithm
: 。
: 我现在的问题是：给出两个有向图，这两个图中的点一一对应。现在要去掉最少的点，
: 使得这两个图都变成无环有向图。
: 请问有没有对这样的问题的定义和现成的算法？

(共1页)

进入CS版参与讨论

相关主题
● Theory的高手们指教一下吧	● 问大家一个有向图的问题
● 请教一个distribution之间的likelihood问题 (转载)	● 说说做系统的经验吧
● 请教一个聚类的问题	● some questions about the geometry
● how to compute binomial distribution without overflow?	● 请问哪儿有现成的minimum vertex cover code
● 问个在图中删除边和点的算法问题 (转载)	● google maps 的data structure 是什么？
● [转载] 我也问一道题	● Valgrind报uninitialized value was created by a heap allocat (转载)
● 牛人来综述一下BN和MN有什么区别?	● [转载] 有搞算法的大侠吗？？？？？问个问题！！！
● 关于有向图的 subgraph mining~~~	● 帮忙找一篇paper

相关话题的讨论汇总
话题: vertex话题: 有向图话题: algorithm话题: feedback话题: set

#	版面	帖数(主题数)
-	全站	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日

历史上的今天