|
|
| Author |
Message |
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 |
|
| Back to top |
|
 |
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. |
|
| Back to top |
|
|
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,
CANADA
avramidi@iro.umontreal.ca Tel (514)343-6111 ext 3511 Fax (514)343-5834
http://www.iro.umontreal.ca/~avramidi |
|
| Back to top |
|
|
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
|
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Nov 21, 2008 4:34 am | All times are GMT
|
|
Mobile Phones | Ringtones | BabbFest | Buy Anything On eBay | Books
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
Other DeniX Solutions sites:
Electronics forum |
Medicine forum |
Unix/Linux blog |
Unix/Linux documentation |
Unix/Linux forums
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
Science and Technology
»
Math
»
Combinatorics
