TUTTE POLYNOMIALS COMPUTABLE IN POLYNOMIAL-TIME

被引：25

作者：

OXLEY, JG ^{[1
]}

WELSH, DJA ^{[1
]}

机构：

[1] UNIV BONN,INST MATH,W-5300 BONN,GERMANY

来源：

DISCRETE MATHEMATICS | 1992年 / 109卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(92)90289-R

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that for any accessible class of matroids of bounded width, the Tutte polynomial is computable in polynomial time.

引用

页码：185 / 192

页数：8

共 17 条

[1]

[Anonymous], 1993, MATROID THEORY

[2] LINEAR TIME ALGORITHMS FOR NP-HARD PROBLEMS RESTRICTED TO PARTIAL K-TREES [J].

ARNBORG, S ;

PROSKUROWSKI, A .

DISCRETE APPLIED MATHEMATICS, 1989, 23 (01) :11-24

[3]

Bixby R. E., 1979, GRAPH THEORY RELATED, P91

[4] COMBINATORIAL MODEL FOR SERIES-PARALLEL NETWORKS [J].

BRYLAWSKI, T .

TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1971, 154 (FEB) :1-+

[5]

Brylawski T.H., 1992, MATROID APPL, V40, P123

[6] A COMBINATORIAL DECOMPOSITION-THEORY [J].

CUNNINGHAM, WH ;

EDMONDS, J .

CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1980, 32 (03) :734-765

[7] ON THE COMPUTATIONAL-COMPLEXITY OF THE JONES AND TUTTE POLYNOMIALS [J].

JAEGER, F ;

VERTIGAN, DL ;

WELSH, DJA .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1990, 108 :35-53

[8]

OXLEY JG, 1979, GRAPH THEORY RELATED, P329

[9] THE COMPLEXITY OF RELIABILITY COMPUTATIONS IN PLANAR AND ACYCLIC GRAPHS [J].

PROVAN, JS .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :694-702

[10] COMPUTATIONAL-COMPLEXITY OF MATROID PROPERTIES [J].

ROBINSON, GC ;

WELSH, DJA .

MATHEMATICAL PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1980, 87 (JAN) :29-45

← 1 2 →