Re: Algorithmic complexity of a graph

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 10/14/04 

Date: 13 Oct 2004 17:56:46 -0700

felixg@techunix.technion.ac.il (Felix Goldberg) wrote in message news:<49fff586.0410080509.41e8e8d5@posting.google.com>...
> 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.

Obviously it's the Kolmogorov complexity of the adjacency matrix,
which can be easily encoded as a bitstring. (Any bitstring
representation should do) Have a look at the lecture notes of
Alexander Shen on the web. (section 'incompressible graphs' IIRC)

http://user.it.uu.se/~vorobyov/Courses/KC/2000/

Regards, 

--
Eray

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: Algorithmic complexity of a graph
    ... > Does by chance anyone know of a definition of the ALGORITHMIC (or ... > I have only found definitions of computational complexity... ... bits necessary to describe a graph in such a system - for instance you ... the number of spanning trees is often called the "complexity" ...
    (sci.math.research)
  • 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)