|
|
| Author |
Message |
sasha mal
science forum beginner
Joined: 05 May 2005
Posts: 21
|
 Posted: Wed Mar 15, 2006 12:48 pm Post subject:
Minimal union of cartesian products
|
|
|
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
2. We generalize the problem to more dimensions.
Let X1,..., Xn be finite sets. The algorithm for the following problem
is needed.
Given a subset Q of the cross product X1 x ... x Xn, find the smallest
natural number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
Could anyone help?
Regards,
sasha |
|
| Back to top |
|
 |
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Thu Mar 16, 2006 5:29 am Post subject:
Re: Minimal union of cartesian products
|
|
|
sasha mal wrote:
| Quote: | Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
|
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
--- Christopher Heckman |
|
| Back to top |
|
|
sasha mal
science forum beginner
Joined: 05 May 2005
Posts: 21
|
| Posted: Thu Mar 16, 2006 11:38 am Post subject:
Re: Minimal union of cartesian products
|
|
|
Proginoskes wrote:
| Quote: | sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
|
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But nevertheless, it's a very nice view of the problem.
Regards,
sasha. |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Fri Mar 17, 2006 8:55 am Post subject:
Re: Minimal union of cartesian products
|
|
|
sasha mal wrote:
| Quote: | Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
|
But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
--- Christopher Heckman |
|
| Back to top |
|
|
sasha mal
science forum beginner
Joined: 05 May 2005
Posts: 21
|
| Posted: Fri Mar 17, 2006 5:17 pm Post subject:
Re: Minimal union of cartesian products
|
|
|
Proginoskes wrote:
| Quote: | sasha mal wrote:
Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
You are right, but that's not what I mean. |
I mean that two Cartesian products are allowed two have common pairs.
For instance, let X={a,b,c}, Y={1,2,3},
Q={(a,1),(a,2),(b,2),(b,3),(c,1),(c,2),(c,3)}.
Then Q={a,c}x{1,2} union {b,c}x{2,3}. This representation is a minimal
one. The pair (c,2) belongs both to
C1 = {a,c}x{1,2} and to C2 = {b,c}x{2,3}.
Howevewr, if you view Q as a bipartite graph, then the complete
subgraphs C1 and C2 do have a common edge. So C1 union C2 is not a
"partition". |
|
| Back to top |
|
|
Proginoskes
science forum Guru
Joined: 29 Apr 2005
Posts: 2593
|
| Posted: Sat Mar 18, 2006 7:26 am Post subject:
Re: Minimal union of cartesian products
|
|
|
sasha mal wrote:
| Quote: | Proginoskes wrote:
sasha mal wrote:
Proginoskes wrote:
sasha mal wrote:
Dear newsgroupers!
1.
Let X and Y be finite sets. The algorithm for the following problem is
needed.
Given a subset Q of the cross product X x Y, find the smallest natural
number k so that Q is equal to the union of k cartesian products.
What is the time complexity of the corresponding problem, i.e.
{<Q,k> | Q is a union of k (or less) Cartesian products}.
[...]
Could anyone help?
You might want to look at bipartite graphs; given Q,X, and Y, define a
bipartite graph G(Q) by V(G) = X union Y, and (x,y) is in E(G) iff
(x,y) is in Q. Then you'll want to partition G into the fewest number
of complete bipartite graphs.
Not quite. Almost. The word "partition" usually means that the sets of
vertices (or edges) of the complete bipartite graphs are disjoint.
However, the Cartesian products are allowed to have common elements.
But if you have common elements in X and Y, they are differentiated in
X x Y by whether they're in the first component or the second. If X =
{1,2,3} and Y={1,2,4}, the ordered pair (1,2) (as an element of X x Y)
indicates that the 1 is from X and the 2 from Y. So the 1's in X and Y
are actually different, when you consider the cross product
X x Y.
You are right, but that's not what I mean.
I mean that two Cartesian products are allowed two have common pairs.
For instance, let X={a,b,c}, Y={1,2,3},
Q={(a,1),(a,2),(b,2),(b,3),(c,1),(c,2),(c,3)}.
Then Q={a,c}x{1,2} union {b,c}x{2,3}. This representation is a minimal
one. The pair (c,2) belongs both to
C1 = {a,c}x{1,2} and to C2 = {b,c}x{2,3}.
Howevewr, if you view Q as a bipartite graph, then the complete
subgraphs C1 and C2 do have a common edge. So C1 union C2 is not a
"partition".
|
Okay; I see what you mean. Yes, "partition" should be replaced with
"union" in my response from so long ago ...
--- Christopher Heckman |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Fri Nov 21, 2008 3:12 am | All times are GMT
|
|
Ringtones | Auto Loans | Debt Consolidation | Mobile Phones | Loans
|
|
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
