Xref: utzoo comp.theory:2100 comp.compilers:2080
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!snorkelwacker.mit.edu!hsdndev!spdcc!iecc!compilers-sender
From: wendt@.cs.colostate.edu (Alan Wendt)
Newsgroups: comp.theory,comp.compilers
Subject: optimal partition into cartesian products?
Keywords: theory, question
Message-ID: <91-06-010@comp.compilers>
Date: 11 Jun 91 17:14:41 GMT
Article-I.D.: comp.91-06-010
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: wendt@.cs.colostate.edu (Alan Wendt)
Organization: Colorado State Computer Science Department
Lines: 18
Approved: compilers@iecc.cambridge.ma.us

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
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.