GENERAL-METHOD FOR THE COMPUTATION OF MATCHING POLYNOMIALS OF GRAPHS

被引：8

作者：

BALAKRISHNARAJAN, MM ^{[1
]}

VENUVANALINGAM, P ^{[1
]}

机构：

[1] BHARATHIDASAN UNIV, DEPT CHEM, Tiruchirappalli 620024, INDIA

来源：

JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES | 1994年 / 34卷 / 05期

关键词：

D O I：

10.1021/ci00021a017

中图分类号：

O6 [化学];

学科分类号：

0703 ;

摘要：

A novel algorithm based on search is developed for computation of matching polynomials of graphs, viewing the edges as ordered pairs. The acyclic Sach's subgraphs of matching polynomials are generated by disjoint-set-union operation. The algorithm is recursive and very general and hence is more compact and has a wide range of applications. The present approach uses artificial intelligence techinques tactfully for partially offsetting combinatorial explosion. This algorithm is more advantageous in terms of space complexity, and its time complexity is exponential as would normally be the case due to nondeterministic polynomial (NP) complete nature of the problem.

引用

页码：1122 / 1126

页数：5

共 45 条

[11]

BARYSZ M, 1986, MATCH-COMMUN MATH CO, V19, P89

[12] INTRODUCTION TO MATCHING POLYNOMIALS [J].

FARRELL, EJ .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (01) :75-86

[13]

GODSIL CD, 1981, CROAT CHEM ACTA, V54, P53

[14]

GORN S, 1965, SYSTEMS COMPUTER SCI

[15]

GRAOVAC A, 1983, CROAT CHEM ACTA, V56, P325

[16]

GROAVAC A, 1987, MATCH-COMMUN MATH CO, V21, P33

[17]

GROAVAC A, 1987, MATCH-COMMUN MATH CO, V21, P81

[18]

GROAVAC A, 1987, MATCH-COMMUN MATH CO, V21, P47

[19]

GURMAN I, 1977, J AM CHEM SOC, V98, P1692

[20] CHARACTERISTIC AND MATCHING POLYNOMIALS OF BENZENOID HYDROCARBONS [J].

GUTMAN, I .

JOURNAL OF THE CHEMICAL SOCIETY-FARADAY TRANSACTIONS II, 1983, 79 :337-345

← 1 2 3 4 5 →