Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
Author Message
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Sun Apr 02, 2006 5:59 am    Post subject: Re: finding maximal directed cycles

Athanassios Avramidis wrote:
 Quote: [...] Thanks, that helped! And it was not homework

I would have found it out wasn't homework, if I had checked your .sig!
8-)

--- Christopher Heckman

 Quote: Thanos Avramidis Researcher, Dept. of Computer Science & Operations Research, Pav. Andre Eisenstadt, Room 3357, Univ. of Montreal, Montreal, H3C 3J7, CANADA avramidi@iro.umontreal.ca Tel (514)343-6111 ext 3511 Fax (514)343-5834 http://www.iro.umontreal.ca/~avramidi
Athanassios Avramidis
science forum beginner

Joined: 29 Mar 2006
Posts: 2

Posted: Sun Apr 02, 2006 3:36 am    Post subject: Re: finding maximal directed cycles

Proginoskes wrote:
 Quote: Athanassios Avramidis wrote: We are given a directed graph (V,E), and, by convention, let any single node induce a directed cycle containing itself. We want to find a partition of the vertex set V (ie sets S_1,...S_k such that \cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j) corresponding to maximal independent cycles, i.e: 1. for each i=1,...,k, there exists a directed cycle over the members of S_i , and 2. there exists no directed cycle spanning nodes across more than one of the S_i Can anyone point to algorithms and complexity for this? If k is part of the input, then the problem is NP-complete, because any algorithm can solve the directed Hamiltonian cycle problem just by letting k=1. There are some digraphs such that no such partition exists. For instance, if you have a strongly-connected digraph which is not (directed) Hamiltonian, you can't have k=1. If k>1, then you should end up with at least two directed cycles; now choose two vertices (u and v), one in S_1 and one in S_2. Since the digraph is strongly connected, there is a directed cycle containing u and v, but this directed cycle violates condition (2). So I think you'll end up partitioning the digraph into strongly connected components, and k will be the number of these. There _is_ an algorithm for this, which I think runs in linear time (linear in the number of vertices + number of edges): It's a DFS algorithm. --- Christopher Heckman P.S. I hope this wasn't homework.

After looking at the issue more carefully, I found that what
I meant to ask was "find the strongly connected components of a
digraph", for which problem Aho et al (pp 189-195) give an
O(max(#nodes,#edges)) algorithm (probably what you had in mind).

Thanks, that helped! And it was not homework :)

--
Thanos Avramidis
Researcher, Dept. of Computer Science & Operations Research,
Pav. Andre Eisenstadt, Room 3357, Univ. of Montreal, Montreal, H3C 3J7,
avramidi@iro.umontreal.ca Tel (514)343-6111 ext 3511 Fax (514)343-5834
http://www.iro.umontreal.ca/~avramidi
Proginoskes
science forum Guru

Joined: 29 Apr 2005
Posts: 2593

Posted: Wed Mar 29, 2006 11:12 pm    Post subject: Re: finding maximal directed cycles

Athanassios Avramidis wrote:
 Quote: We are given a directed graph (V,E), and, by convention, let any single node induce a directed cycle containing itself. We want to find a partition of the vertex set V (ie sets S_1,...S_k such that \cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j) corresponding to maximal independent cycles, i.e: 1. for each i=1,...,k, there exists a directed cycle over the members of S_i , and 2. there exists no directed cycle spanning nodes across more than one of the S_i Can anyone point to algorithms and complexity for this?

If k is part of the input, then the problem is NP-complete, because any
algorithm can solve the directed Hamiltonian cycle problem just by
letting k=1.

There are some digraphs such that no such partition exists. For
instance, if you have a strongly-connected digraph which is not
(directed) Hamiltonian, you can't have k=1. If k>1, then you should end
up with at least two directed cycles; now choose two vertices (u and
v), one in S_1 and one in S_2. Since the digraph is strongly connected,
there is a directed cycle containing u and v, but this directed cycle
violates condition (2).

So I think you'll end up partitioning the digraph into strongly
connected components, and k will be the number of these. There _is_ an
algorithm for this, which I think runs in linear time (linear in the
number of vertices + number of edges): It's a DFS algorithm.

--- Christopher Heckman

P.S. I hope this wasn't homework.
Athanassios Avramidis
science forum beginner

Joined: 29 Mar 2006
Posts: 2

 Posted: Wed Mar 29, 2006 1:26 am    Post subject: finding maximal directed cycles We are given a directed graph (V,E), and, by convention, let any single node induce a directed cycle containing itself. We want to find a partition of the vertex set V (ie sets S_1,...S_k such that \cup_i S_i = V and S_i \cap S_j = \empty whenever i \ne j) corresponding to maximal independent cycles, i.e: 1. for each i=1,...,k, there exists a directed cycle over the members of S_i , and 2. there exists no directed cycle spanning nodes across more than one of the S_i Can anyone point to algorithms and complexity for this? Neither of the books by - Aho, Hopcroft and Ulmann - Bondy and Murty (Graph theory and Applications) seems to provide an answer. -- Thanos Avramidis Researcher, Dept. of Computer Science & Operations Research, Pav. Andre Eisenstadt, Room 3357, Univ. of Montreal, Montreal, H3C 3J7, CANADA avramidi@iro.umontreal.ca Tel (514)343-6111 ext 3511 Fax (514)343-5834 http://www.iro.umontreal.ca/~avramidi

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Sat Apr 20, 2019 2:14 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

 Topic Author Forum Replies Last Post Similar Topics Finding a Web Design Development with a Good Results lbardagol@gmail.com Math 0 Mon Jul 17, 2006 10:21 am Maximal dimension + subspace of invertible matrices eugene Math 3 Thu Jul 13, 2006 8:04 pm Request for help finding a 1/4-32 or 1/4-40 screw, or thr... John2005 Mechanics 3 Sun Jul 02, 2006 2:15 am Maximal entropy from Bayes' law? John Baez Research 9 Thu Jun 29, 2006 9:05 pm Help Finding Lab Supply: Fussy about Bench Paper Peggy.Dunlop@ec.gc.ca Chem 4 Sun Jun 18, 2006 10:06 pm