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 |