Fast algorithms for K4 immersion testing

被引：9

作者：

Booth, HD ^{[1
]}

Govindan, R

Langston, MA

Ramachandramurthi, S

机构：

[1] Univ Tennessee, Dept Comp Sci, Knoxville, TN 37996 USA

[2] Qualcomm Inc, San Diego, CA 92121 USA

[3] LSI Log Corp, Waltham, MA 02451 USA

来源：

JOURNAL OF ALGORITHMS | 1999年 / 30卷 / 02期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1006/jagm.1998.0991

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Many useful classes of graphs can in principle be recognized with finite batteries of obstruction tests. One of the most fundamental tests is to determine whether an arbitrary input graph contains K-4 in the immersion order. In this paper, we present for the first time a fast, practical algorithm to accomplish this task. We also extend our method so that, should an immersed K-4 be present, a K-4 model is isolated. (C) 1999 Academic Press.

引用

页码：344 / 378

页数：35

共 21 条

[1]

Bodlaender H. L., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P226, DOI 10.1145/167088.167161

[2] POLYNOMIAL-TIME SELF-REDUCIBILITY - THEORETICAL MOTIVATIONS AND PRACTICAL RESULTS [J].

BROWN, DJ ;

FELLOWS, MR ;

LANGSTON, MA .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1989, 31 (1-2) :1-9

[3]

Dirac G., 1960, MATH NACHR, V22, P61, DOI DOI 10.1002/MANA.19600220107

[4] TOPOLOGY OF SERIES-PARALLEL NETWORKS [J].

DUFFIN, RJ .

JOURNAL OF MATHEMATICAL ANALYSIS AND APPLICATIONS, 1965, 10 (02) :303-&

[5]

Even S., 1976, Theoretical Computer Science, V2, P339, DOI 10.1016/0304-3975(76)90086-4

[6] ON WELL-PARTIAL-ORDER THEORY AND ITS APPLICATION TO COMBINATORIAL PROBLEMS OF VLSI DESIGN [J].

FELLOWS, MR ;

LANGSTON, MA .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (01) :117-126

[7] ON SEARCH, DECISION, AND THE EFFICIENCY OF POLYNOMIAL-TIME ALGORITHMS [J].

FELLOWS, MR ;

LANGSTON, MA .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) :769-779

[8]

Ford L., 1974, Flows in networks

[9] A HEURISTIC ALGORITHM FOR GATE ASSIGNMENT IN ONE-DIMENSIONAL ARRAY APPROACH [J].

FUJII, T ;

HORIKAWA, H ;

KIKUNO, T ;

YOSHIDA, N .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (02) :159-164

[10]

FUSSELL D, 1989, P 16 INT C AUT LANG, V372, P379

← 1 2 3 →