From: Catalin Dima <cdima@inrialpes.fr>
Subject: Re: Matrices and graph theory
Date: Tue, 29 Feb 2000 17:19:22 +0000
Newsgroups: sci.math
Summary: [missing]

Hi,

>
> Can someone please point up possible matrix operations that can be
> applied to such matrix representations of graphs to generate transformed
> matrices that reveal fundamental properties of the graph?

>
> I'm thinking of some successive series of operations which would
> transform the original adjacency/incidence matrices into say a matrix of
> shortest routes between node pairs.
>

They are adaptations of the classical addition and multiplication of
matrices. For each semiring R, the nxn square matrices over R form a
semiring too. Floyd-Warshall's algorithm for computing the length of the
shortest path can be stated in this framework.

Try adapting this algorithm by considering the semiring of lists in which
the first operation is taking the list of minimal length and the second is
list concatenation. (well, I hope it's a semiring ;-) )

>
> Can anyone give me pointers to where I can find information about this
> sort of thing?

Hard question... I find them rather folklore. The reference below on max+
algebra might provide some references to start from. You might also search
the web or some collection of technical reports, like www.ncstrl.org, for
the "semiring" keyword. Anyway, research is quite active in the field. Many
theoretical computer scientists work on the field: Salomaa, Backhouse,
Kozen, Bloom, Esik, Krob are just a few names.

Look, I found a reference that seems to fit what you want: Roland Backhouse
and B. Carre, Regular algebra applied to path-finding problems, J. Inst.
Math. Appl. (?!) vol 15, p.161-186, 1975.


> I would also be interested in a basic explanation of
> eigenvector/value methods and their possible value in graph
> theory/network analysis.
>

Well, I would be interested too in these... Maybe you should post this
question to the comp.theory newsgroup.

>
> It's been suggested that Max+ and Min+ algebras might be useful to me in
> terms of shortest route finding, does anyone know where I could find a
> reasonable introduction to these?
>

Try http://amadeus.inria.fr/gaubert/introductive.html
There you may find some introductory papers of Stephane Gaubert on max+
algebra.

Success,
Catalin.
==============================================================================

From: a_wol@my-deja.com
Subject: Re: Matrices and graph theory
Date: Tue, 07 Mar 2000 11:06:55 GMT
Newsgroups: sci.math

Hi,

Thanks for the reply to my query about matrix operations that can be
applied to matrix representations of graphs to generate transformed
matrices that reveal fundamental properties of the graph.

I found some resources on Max Plus algebra on the web:

http://cttrailf.ct.tudelft.nl/verkeerskunde/staff/goverde/homepage.html
has slides describing a Max Plus algebra approach for transportation
problems

http://www.cs.umd.edu/~cema/MaxPlus/980701/
has a seminar giving an introduction to Max Plus algebra.

In article <38BBFF9A.9D93BB3E@inrialpes.fr>,
  Catalin Dima <cdima@inrialpes.fr> wrote:

> Look, I found a reference that seems to fit what  you want: Roland
> Backhouse and B. Carre, Regular algebra applied to  path-finding
> problems, J. Inst. Math. Appl. (?!) vol 15, p.161-186, 1975.
Thanks for that.  Another reference I found (as a result of that ) was
B.A. Carre, An Algebra for Network Routing Problems, J. Inst. Math.
Appl. Vol 7, p.273-294, 1971

Julia


Sent via Deja.com http://www.deja.com/
Before you buy.