Re: Algorithmic complexity of a graph

From: Felix Goldberg (felixg_at_techunix.technion.ac.il)
Date: 10/08/04 

Date: 8 Oct 2004 06:09:46 -0700

caterina <caterina.mora@uibk.ac.at> wrote in message news:<rwff2c1dqg8q@legacy>...
> Hi!
>
> I don't know if this is the right place to ask this question, but I
> have no other ideas...
>
> Does by chance anyone know of a definition of the ALGORITHMIC (or
> Kolmogorov) complexity of a graph? And, in case, could you suggest
> where I could look for it?
>
> I have only found definitions of computational complexity...
>
> Thanks a lot!!!
>
> cat

Well, I reckon you could fix some system of notation and count the
bits necessary to describe a graph in such a system - for instance you
could count the 1's in the adjacency matrix.

Apropos, the number of spanning trees is often called the "complexity"
of a graph. Depending on your needs, you might find this a useful
messure too.

HTH,
Felix.

Relevant Pages

  • Re: kung fu mereotopology
    ... the algebraic approach to computational complexity ... because the homology of graph complexes ... that much of the operad theory on which this is built ... that ties their algebraics to more classical work on matroidshttp://www.springerlink.com/content/y60n827057m374n8/ ...
    (sci.math)
  • Re: kung fu mereotopology
    ... Can you point to a sentence of Kontsevich related to ... the algebraic approach to computational complexity ... because the homology of graph complexes ... that ties their algebraics to more classical work on matroids ...
    (sci.math)
  • Re: Arrays as key in a HashMap
    ... Just because you have a contract about an interface, and it can be kept constant, does not mean that the code behind it needs to be as complicated as you can manage, or want to, create it. ... Can you solve that problem with less complexity, or do you just move the complexity elsewhere? ... The hash code is, of course, an optimization to avoid a linear search... ... But, using a hash code of the graph as a unique identifier of the graph is not the way to go, as you then have to take into consideration many factors that are quite complex, such as ...
    (comp.lang.java.programmer)
  • Re: Graph Theory: Cutting a Graph into Two in an Artificial Chemistry
    ... I start with a graph that has a single connected component (such that ... then I count that as a valid way that my original graph ... The set of all 'valid' splits from is the answer I want. ... It would probably be useful to know the size and complexity of the ...
    (sci.math)
  • Algorithmic complexity of a graph
    ... Does by chance anyone know of a definition of the ALGORITHMIC (or ... Kolmogorov) complexity of a graph? ... I have only found definitions of computational complexity... ...
    (sci.math.research)