optimal partition into cartesian products?

Article View: comp.theory

Article #1794

#1794

From: wendt Alan Wendt
Date: Tue, 11 Jun 1991 17:14

18 lines
1381 bytes

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.

Technical Details

Message-ID: <91-06-010@comp.compilers>

Path:

arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!spool.mu.edu!snorkelwacker.mit.edu!hsdndev!spdcc!iecc!compilers-sender

Show Full Headers

Complete Article Headers

Path: arc1-ca.pugleaf.net!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