t*****k
发帖数: 390 | 1 For a directed graph without cycles, if I removed some paths from this graph
(does not mean removing edges), how can I reconstruct the graph without the
se edges easily? Thanks!
If someone knows the references, that will be also good :) Many thanks! |
s******e
发帖数: 285 | 2 没看懂你说什么，不如用中文表述吧。。。
graph
the
【在 t*****k 的大作中提到】
: For a directed graph without cycles, if I removed some paths from this graph
: (does not mean removing edges), how can I reconstruct the graph without the
: se edges easily? Thanks!
: If someone knows the references, that will be also good :) Many thanks!
|
v********e
发帖数: 1058 | 3 me neither
【在 s******e 的大作中提到】
: 没看懂你说什么，不如用中文表述吧。。。
:
: graph
: the
|
m*****f
发帖数: 1243 | 4 if I removed some paths from this graph
(does not mean removing edges)
???? |
z1
发帖数: 389 | 5 path is consisit of edges ...
graph
the
【在 t*****k 的大作中提到】
: For a directed graph without cycles, if I removed some paths from this graph
: (does not mean removing edges), how can I reconstruct the graph without the
: se edges easily? Thanks!
: If someone knows the references, that will be also good :) Many thanks!
|
t*****k
发帖数: 390 | 6 比如graph里有4条paths：A->B->C->D, E->B->C->F, E->B->C->D, A->B->C->F，我rem
ove掉前2条paths，但保留后两条，有没有可能重新reconstruct graph实现这个目的，
可以加一些dummy nodes...
graph
the
【在 t*****k 的大作中提到】
: For a directed graph without cycles, if I removed some paths from this graph
: (does not mean removing edges), how can I reconstruct the graph without the
: se edges easily? Thanks!
: If someone knows the references, that will be also good :) Many thanks!
|
v********e
发帖数: 1058 | 7 i still don't understand. what is "reconstuct graph"?
rem
【在 t*****k 的大作中提到】
: 比如graph里有4条paths：A->B->C->D, E->B->C->F, E->B->C->D, A->B->C->F，我rem
: ove掉前2条paths，但保留后两条，有没有可能重新reconstruct graph实现这个目的，
: 可以加一些dummy nodes...
:
: graph
: the
|
t*****k
发帖数: 390 | 8 这个问题是这样的，你可以认为是找longest paths。
对一个图来说，每个edge都有一个weight，我要找一条path，构成他的edge的weight之
和最大...
现在我要从这个 graph中抽出N条paths出来，找这个graph中除去这N条paths后最longe
st 的path
【在 v********e 的大作中提到】
: i still don't understand. what is "reconstuct graph"?
:
: rem
|
v********e
发帖数: 1058 | 9 finding longest path is NP hard
longe
【在 t*****k 的大作中提到】
: 这个问题是这样的，你可以认为是找longest paths。
: 对一个图来说，每个edge都有一个weight，我要找一条path，构成他的edge的weight之
: 和最大...
: 现在我要从这个 graph中抽出N条paths出来，找这个graph中除去这N条paths后最longe
: st 的path
|
h*******e
发帖数: 225 | 10 His original post said it was a DAG, then you can use DP.
【在 v********e 的大作中提到】
: finding longest path is NP hard
:
: longe
|
v********e
发帖数: 1058 | 11 orz.. when reading his last post, i then ignored his first one.. -_-b
【在 h*******e 的大作中提到】
: His original post said it was a DAG, then you can use DP.
|
