optimal partition into cartesian products?

wendt@.cs.colostate.edu (Alan Wendt)
11 Jun 91 17:14:41 GMT

          From comp.compilers

Related articles
optimal partition into cartesian products? wendt@.cs.colostate.edu (1991-06-11)
Re: optimal partition into cartesian products? sbloch@euler.UCSD.EDU (1991-06-12)
| List of all articles for this month |

Newsgroups: comp.theory,comp.compilers
From: wendt@.cs.colostate.edu (Alan Wendt)
Keywords: theory, question
Organization: Colorado State Computer Science Department
Date: 11 Jun 91 17:14:41 GMT

I've got a theoretical problem I'm hoping someone can give me a citation
for. I'm trying to partition a subset of a n-dimensional cartesian product
into a miniumum number of cartesian products. For example, if n=2,
A = {a,b,c} and B = {d,e,f}, I might have a subset {ad,bd,be,cd,ce,cf} and
I want to find the minimum # of rectangles needed to tile the triangle
in the diagram below (answer=3). A general solution would of course allow
for arbitrary n and for moving rows and columns around in the diagram.




                                a x
                                b x x
                                c x x x
                                        d e f


Alan Wendt
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.