POLYNOMIAL-TIME SELF-REDUCIBILITY - THEORETICAL MOTIVATIONS AND PRACTICAL RESULTS

被引：17

作者：

BROWN, DJ

FELLOWS, MR

LANGSTON, MA

机构：

[1] UNIV IDAHO, DEPT COMP SCI, MOSCOW, ID 83843 USA

[2] WASHINGTON STATE UNIV, DEPT COMP SCI, PULLMAN, WA 99164 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS | 1989年 / 31卷 / 1-2期

关键词：

D O I：

10.1080/00207168908803783

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

引用

页码：1 / 9

页数：9

共 30 条

[1]

ABRAHAMSON K, 1988, CS88191 WASH STAT U

[2] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS [J].

BOOTH, KS ;

LUEKER, GS .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) :335-379

[3]

BRYANT RL, 1987, 25TH P ALL C COMM CO, P397

[4] KNOTS AND LINKS IN SPATIAL GRAPHS [J].

CONWAY, JH ;

GORDON, CM .

JOURNAL OF GRAPH THEORY, 1983, 7 (04) :445-453

[5] EXACT AND APPROXIMATE SOLUTIONS FOR THE GATE MATRIX LAYOUT PROBLEM [J].

DEO, N ;

KRISHNAMOORTHY, MS ;

LANGSTON, MA .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :79-84

[6]

Fellows M., 1989, 21 ACM S THEOR COMP, P501

[7] NONCONSTRUCTIVE TOOLS FOR PROVING POLYNOMIAL-TIME DECIDABILITY [J].

FELLOWS, MR ;

LANGSTON, MA .

JOURNAL OF THE ACM, 1988, 35 (03) :727-739

[8] NONCONSTRUCTIVE ADVANCES IN POLYNOMIAL-TIME COMPLEXITY [J].

FELLOWS, MR ;

LANGSTON, MA .

INFORMATION PROCESSING LETTERS, 1987, 26 (03) :157-162

[9]

FELLOWS MR, 1988, 5TH P MIT C ADV RES, P315

[10]

FRIEDMAN H, IN PRESS APPLICATION

← 1 2 3 →