🚀 go-pugleaf

From: ihnp4!wucs1!wuccrc!jst@rsch.wisc.edu (Jon Turner)
Subject: anyone heard of this problem?

I have a student who is interested in register allocation on machines
with multiple register types. As with most register allocation problems
it can be formalized as a pebble game or a graph layout problem. The
graph layout formulation of the particular version we're interested in
goes like this.
     
Given a directed tree T=(V,E) in which each internal node has two
incoming edges and each node but the root has one outgoing edge,
a subset B of E, (called the black edges, the others are white)
and integers b and w.
     
Is there a function f from V to the positive integers such that
     
    1. f(u) < f(v) implies there is no path from v to u in T
    2. for all i, |H(i)| <= b where
     
        H(i) = { (x,y) | (x,y) is in B and f(x) <= i < f(y) }
     
    3. for all i, |J(i)| <= w where
     
        J(i) = { (x,y) | (x,y) is in E-B and f(x) <= i < f(y) }
     
Restating, we want to know if there is a monotone layout of T such
that the number of black edges crossing any point is at most b,
and the number of white edges is at most w.
     
If you replace T with a dag, the problem is NP-complete. This follows
trivially from the NP-completeness of register allocation on dags
with just one register type. The problem can be solved in polyomial
time for trees with one register type, but the complexity of the version
given here (trees with two register types) appears to be open.
     
I would appreciate hearing from anyone who knows of any results for
this problem. Thanks in advance.
     
Jon Turner     Washington University in St. Louis 314-889-6193
UUCP:        jst@wucs.UUCP  or  ..!{ihnp4,seismo}!wucs!jst
ARPANET:    wucs!jst@seismo.ARPA
CSNET:        wucs!jst%seismo.ARPA@csnet-relay or
        wucs!jst.uucp%bbncv.ARPA@csnet-relay