On Some Classes of Problems on Graphs

EasyChair Preprint 1156

Abstract

At present Graph Theory is widely applied for resolving theoretic and applied problems. For this reason, classications of the problems of Graph Theory according to the complexity of their resolving is one of the actual problems. In the given paper this problem is investigated on the base of space complexity dened in terms of data structures used for the representation of analyzed graphs, orgraphs, and directed graphs. The following two non-trivial the simplest sets of problems of Graph Theory are investigated in detail. The rst set consists of problems that can be resolved by some algorithm with space complexity that is linear relative to the size of memory necessary for the data structure that represents the analyzed graphs. The second set consists of problems that can be resolved by some algorithm that operates on space that is linear relative to the size of memory necessary for the data structure that represents the analyzed graphs but additionally uses some additional memory of the same size intended for sequential generation of the designed object or objects. Some characteristics for the problems of Graph Theory that are in or out of these classes are given.

Keyphrases: Algorithms, complexity, graphs

@booklet{EasyChair:1156,
  author    = {Volodymyr G. Skobelev},
  title     = {On Some Classes of Problems on Graphs},
  howpublished = {EasyChair Preprint 1156},
  year      = {EasyChair, 2019}}