×

Interpretation on graphs and complexity characteristics of a search for specific patterns. (English. Russian original) Zbl 0737.68065

Autom. Doc. Math. Linguist. 23, No. 1, 37-45 (1989); translation from Nauchno-Tekh. Inf., Ser. 2 1989, No. 1, 23-27 (1989).
Summary: An interpretation on graphs is suggested of a search for patterns by the JSM method of automatic hypothesis generation. The interpretation establishes a connection between a search for JSM-hypotheses and a study of classical combinatoric objects (bipartite graphs and complete bipartite subgraphs in them). A relationship is thus established with other pattern search systems. Algorithmic complexity (polynomial calculability, \(NP\)-completeness, and \(\neq P\)-completeness) of certain pattern search problems is described (this also refers to a search for subgraphs of a certain type in bipartite graphs.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite