ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 5, 49, 90 Perepelitsa, Vitaliy, Kochkarov, Ahmat, Karachai-Cherkes Technological Institute, Russia Fractal Graphs and Their Properties This work is devoted to foundation of following fundamental characteristics of fractal (pre-fractal) graphs: fractal dimension computing complexity of problem of recognition of pre-fractal property, estimations of complexity of NP-full problems on fractal graphs. In particular, if initiator is n - vertices graph then in the case of compression coefficient ρ < 1 fractal graph has fractal dimension which strictly greater than topological dimension. If initiator is homogeneous graph with degree 1 or 2 then recognition of pre-fractal property is polynomial solvable problem.

Reference: V. Perepelitsa, V. Pinchuk, L. Sergeeva, A. Pozdnjakova, Fractal Graphs and their Properties, IKM’97, Digital Proceedings (www. uni. -weimar. de).