Backtrack search algorithms and the maximal common subgraph problem

Software - Practice and Experience - Tập 12 Số 1 - Trang 23-34 - 1982
James J. McGregor1
1Department of Computer Science, University of Sheffield, Sheffield S10 2TN, U.K.

Tóm tắt

AbstractBacktrack algorithms are applicable to a wide variety of problems. An efficient but readable version of such an algorithm is presented and its use in the problem of finding the maximal common subgraph of two graphs is described. Techniques available in this application area for ordering and pruning the backtrack search are discussed. This algorithm has been used successfully as a component of a program for analysing chemical reactions and enumerating the bond changes which have taken place.

Từ khóa


Tài liệu tham khảo

10.1016/0160-9327(68)90097-5

10.1021/c160016a007

10.1021/bk-1977-0046.ch001

Lynch M. F., 1978, The automatic detection of chemical reaction sites, J. Chem. Inf. Comp. Sci., 18, 10.1021/ci60015a009

McGregor J. J., 1981, Use of a maximal common subgraph algorithm in the automatic identification of the ostensible bond changes occurring in chemical reactions, J. Chem. Inf. Comp. Sci., 21, 10.1021/ci00031a005

Ievi C., 1972, A note on the derivation of maximal common subgraphs of two directed or undirected graphs, Calcolo, 9, 1

10.1021/ja00465a041

10.1145/321296.321300

10.1145/321510.321511

10.1145/362515.362562

Flaray F., 1969, Graph Theory

S. A.Cook ‘The complexity of theorem proving procedures’ inProceedings of the 3rd Annual ACM Symposium on Theory of Computing 1971 pp.151–158.

10.1145/321921.321925

Barrow H. G., 1972, Frontiers of Pattern Recognition

Freuder E. C., 1976, Pattern Recognition and Artificial Intelligence

Thông tin
Thông tin xuất bản

Software - Practice and Experience

Tập 12 Số 1

23-34

Thông tin tác giả