2011-09-20
Re: HW2 Problem 1.14.
Originally Posted By: jnewth
In 1.14C I think I have a strategy but wanted to get some feedback. Essentially, each of these problems can be shown to be in P if one can find a deterministic polynomial algorithm that decides it. My strategy for BIPARTITE is to pick a node, assign it to A, and then assign all its nodes to B. Then, for each of those nodes, follow their links and assign them to A. If there is ever an instance when a node is in one partition and needs to be assigned to the other, stop and reject G.
My question is, how can we know that all the nodes are visited? What assumptions can we make about the graph? Are all these links one-way? Am I barking up the wrong tree?
My question is, how can we know that all the nodes are visited? What assumptions can we make about the graph? Are all these links one-way? Am I barking up the wrong tree?
'''Originally Posted By: jnewth'''
In 1.14C I think I have a strategy but wanted to get some feedback. Essentially, each of these problems can be shown to be in P if one can find a deterministic polynomial algorithm that decides it. My strategy for BIPARTITE is to pick a node, assign it to A, and then assign all its nodes to B. Then, for each of those nodes, follow their links and assign them to A. If there is ever an instance when a node is in one partition and needs to be assigned to the other, stop and reject G. <br><br>My question is, how can we know that all the nodes are visited? What assumptions can we make about the graph? Are all these links one-way? Am I barking up the wrong tree?
Originally Posted By: jnewth
In 1.14A are a pair [u,v] connected in G only if there exists a direct path? Or any path at all (like u->z->q->d->v)?
EDIT: Ah, it's been a long time since I've thought about graphs. I think a path in this case is a simple path (see part d), meaning, it can contain multiple edges. An edge is a connection between two vertices.
EDIT: Ah, it's been a long time since I've thought about graphs. I think a path in this case is a simple path (see part d), meaning, it can contain multiple edges. An edge is a connection between two vertices.
'''Originally Posted By: jnewth'''
In 1.14A are a pair [u,v] connected in G only if there exists a direct path? Or any path at all (like u->z->q->d->v)?<br><br>EDIT: Ah, it's been a long time since I've thought about graphs. I think a path in this case is a simple path (see part d), meaning, it can contain multiple edges. An edge is a connection between two vertices.
2011-09-21
Originally Posted By: asingh
1.14 c)
Using DFS (depth first search), have a flag at each node and that way you can remember it later.
Using DFS (depth first search), have a flag at each node and that way you can remember it later.
'''Originally Posted By: asingh'''
1.14 c)<br><br>Using DFS (depth first search), have a flag at each node and that way you can remember it later.
Originally Posted By: asingh
1.14 A)
It has to be a direct path from s to t. (if the problem is for going from s to t.)
It has to be a direct path from s to t. (if the problem is for going from s to t.)
'''Originally Posted By: asingh'''
1.14 A)<br><br>It has to be a direct path from s to t. (if the problem is for going from s to t.)
2011-09-24
Originally Posted By: asingh
@1.14 a)
I guess I misinterpreted the question. Jnewth, you could be right about connectivity.
...Ashu
I guess I misinterpreted the question. Jnewth, you could be right about connectivity.
...Ashu
'''Originally Posted By: asingh'''
@1.14 a)<br><br>I guess I misinterpreted the question. Jnewth, you could be right about connectivity.<br><br><br>...Ashu
(c) 2024 Yioop - PHP Search Engine