Title :
Kolmogorov random graphs
Author :
Buhrman, Harry ; Li, Ming ; Vitányi, Paul
Author_Institution :
CWI, Amsterdam, Netherlands
Abstract :
We investigate topological, combinatorial, statistical, and enumeration properties of finite graphs with high Kolmogorov complexity (almost all graphs) using the novel incompressibility method. Example results are: (i) the mean and variance of the number of (possibly overlapping) ordered labeled subgraphs of a labeled graph as a function of its randomness deficiency and (ii) a new elementary proof for the number of unlabeled graphs
Keywords :
computational complexity; graph theory; random processes; statistical analysis; Kolmogorov complexity; Kolmogorov random graphs; combinatorial properties; enumeration properties; finite graphs; incompressibility method; labeled graph; mean; ordered labeled subgraphs; randomness deficiency; statistical properties; topological properties; variance; Analog integrated circuits; Computer science; Frequency; Noise measurement; Random number generation; Testing;
Conference_Titel :
Compression and Complexity of Sequences 1997. Proceedings
Conference_Location :
Salerno
Print_ISBN :
0-8186-8132-2
DOI :
10.1109/SEQUEN.1997.666905
