Matrices for binary relations? Fwd: TOPIC:Sequences

[Antti Karttunen]

With Kristjan's permit, I'll post his question to the list:
If you reply, please include his address s040321 at student.dtu.dk
on the To:-line, as he is not a memeber of SeqFan-list.

---------- Forwarded message ----------
From: Kristjan Haukur Flosason <s040321 at student.dtu.dk>
Date: Nov 22, 2005 5:07 PM
Subject: TOPIC:Sequences
To: antti.karttunen<#>gmail.com


Hi Antti,

I am working on my M.Sc. thesis in electrical engineering at DTU in Denmark
and I got stuck in a combinatorial problem. I need to generate a number of
alternative solutions that will later be examined for feasibility. Since I
saw your name on the Encyclopedia of Integer Sequences, I thought you might
have a hint for me. The problem formulation I am facing is the following:

Given are n objects x1…xn and binary relational matrix FRij. The objects are
to be assigned to slots where each slot can contain one or more objects. Two
objects xi and xj can only exist in the same slot if their relation is given
with FRij = 1. FRij = 1 does not force the objects into the same slot. How
many alternative assignments are possible?

Moreover: Which algorithm can be used to *efficiently* find all alternative
assignments?

Do you have a hint on how to approach a solution, where to find www
resources or other hints?

Best regards,

--------------------------------

Kristján Haukur Flosason

stud.nr. s040321



Ørsted-DTU, Automation

 - byg. 326, rum 117 -

DK 2800, Kgs. Lyngby

Mobile: 2964 3674

E-mail: s040321 at student.dtu.dk

--------------------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20051124/649e01e2/attachment.htm>