![]() | ![]() |
|
Algorithms Algorithms and Data Structures - Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum |
![]() |
| LinkBack | Thread Tools | Display Modes |
October 31st, 2009, 11:58 AM | #1 | |
Joined: Oct 2009 Posts: 4 | Finding an acyclic orientation in a graph
Hi, I'm having some difficulty with the following question: Quote:
Thanks in advance! | |
![]() |
My Computer Forum is free to register and we welcome everyone! |
January 20th, 2010, 11:42 PM | #2 |
Joined: Dec 2009 Posts: 7 | Re: Finding an acyclic orientation in a graph
Hi, The problem is NP-Hard. It can be easily reduced to Hamiltonian cycle problem. And no polynomial time algorithm is known for Hamiltonian cycle. I am not sure if any approximation algorithm exists ? |
![]() |
January 21st, 2010, 05:05 AM | #3 | |
Joined: Oct 2009 Posts: 4 | Re: Finding an acyclic orientation in a graph
Hi, Thanks for the reply. Here is the solution for the problem: Quote:
| |
![]() |
January 21st, 2010, 09:22 AM | #4 |
Joined: Dec 2009 Posts: 7 | Re: Finding an acyclic orientation in a graph
This is a very interesting observation. Thanks. Since I have learned NP-completeness, rather than finding if polynomial time algorithm for a problem I tend to prove it NP-hard. |
![]() |
January 24th, 2010, 03:20 AM | #5 |
Joined: Dec 2009 Posts: 7 | Re: Finding an acyclic orientation in a graph
How about this counter example? It has a directed cycle and a vertex that has zero out degree. Do you have a proof of your algorithm? |
![]() |
January 24th, 2010, 03:42 AM | #6 |
Joined: Oct 2009 Posts: 4 | Re: Finding an acyclic orientation in a graph
The algorithm takes as input an undirected graph and a function D:V->N. Could you please explicitly state the two for you counter example? |
![]() |
January 24th, 2010, 12:17 PM | #7 |
Joined: Dec 2009 Posts: 7 | Re: Finding an acyclic orientation in a graph
This is an example of an orientation with a directed cycle and a zero out degree vertex. I am yet not sure about the D:V-N function. If you could give an example input I might specify the function for this instance. |
![]() |
January 24th, 2010, 12:28 PM | #8 | |
Joined: Oct 2009 Posts: 4 | Re: Finding an acyclic orientation in a graph Quote:
The algorithms then concludes if G has an acyclic orientation G' such that for each v in V , its out-degree (the number of edges going out of it) in G' is D(v). For example, a legal input would be: G={V,E} V={a,b,c} E={(a,b),(b,c),(c,a)} D:V->N D(a)=1 D(b)=1 D(c)=0 This means that we want the result graph to have one edge going out of a, one out of b, and no edges going out of c. The algorithm is supposed to tell us if for the given input, an acyclic orientation is possible. | |
![]() |
![]() |
|
Tags |
acyclic, finding, graph, orientation |
Thread Tools | |
Display Modes | |
|
![]() | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
help me for finding gboxapp software | jamiulislam | Computer Science | 0 | January 21st, 2013 02:02 AM |
Help in finding a high performance notebook! | deanSs | Computer Hardware | 2 | February 9th, 2012 12:55 PM |
decide if a graph contains a triangle | becko | Algorithms | 2 | December 28th, 2011 11:50 AM |
Finding large 2-primes | NClement | Computational Science | 13 | August 7th, 2008 05:03 AM |
Finding clusters of points on a grid | circleBounding | Algorithms | 2 | February 10th, 2008 05:09 PM |