DocumentCode
2291740
Title
Kolmogorov random graphs
Author
Buhrman, Harry ; Li, Ming ; Vitányi, Paul
Author_Institution
CWI, Amsterdam, Netherlands
fYear
1997
fDate
11-13 Jun 1997
Firstpage
78
Lastpage
96
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Compression and Complexity of Sequences 1997. Proceedings
Conference_Location
Salerno
Print_ISBN
0-8186-8132-2
Type
conf
DOI
10.1109/SEQUEN.1997.666905
Filename
666905
Link To Document