asymptotic behaviour of multivariate recurrence equations?

Hello,

I am interested in exponential algorithms and currently I am playing around
with (bounded) search trees. Often such an approach leads to homogeneous
linear recurrences in a single variable. For these it is enough to compute
the real root of its characteristic polynomial with max absolute value and
we know the basis of the asymptotic behaviour.

Now what happens with multivariate recurrence equations? For example I have:

T(n,m) = T(n,m-5) + 5 T(n-1,m-5) + 10 T(n-2,m-5) + 10 T(n-3,m-5) + 5

T(n-4,m-5) for n>5 and m> 5

and T(n,m) = 1 for n<=5 or m <=5

Simplified this can of course be written as:

T(n,m') = T(n,m'-1) + 5 T(n-1,m'-1) + 10 T(n-2,m'-1) + 10 T(n-3,m'-1) + 5

T(n-4,m'-1) n>5 and m>5

T(n,m) = 1 for n<=5 or m'<=1

m':= 5m,



Here m are the edges of a graph with n nodes, therefore m <= n(n-1)/2.

How do I compute the smallest c such that T(n,m) = O(c^n) ? What general
approaches are there? I looked in the book by Graham Knuth Patashnik but
they only solve univariate rec eq. and they try to do this exactly which is
not my focus here. I also considered using the Maple package combstruct
(a.k.a.

Lambda, Upsilon, Omega) but somehow I don't see how to apply it to get the
asymptotic behaviour.

Thanks in advance for any help,

Marc Nunkesser.


.