AN INCREMENTAL LINEAR-TIME ALGORITHM FOR RECOGNIZING INTERVAL-GRAPHS

被引：107

作者：

KORTE, N ^{[1
]}

MOHRING, RH ^{[1
]}

机构：

[1] TECH UNIV BERLIN, FACHBEREICH MATH MA61, D-1000 BERLIN 12, FED REP GER

来源：

SIAM JOURNAL ON COMPUTING | 1989年 / 18卷 / 01期

关键词：

D O I：

10.1137/0218005

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：68 / 81

页数：14

共 11 条

[1] 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

[2] 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

[3] INCIDENCE MATRICES AND INTERVAL GRAPHS [J].

FULKERSON, DR ;

GROSS, OA .

PACIFIC JOURNAL OF MATHEMATICS, 1965, 15 (03) :835-+

[4]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH

[5] INTERVAL-GRAPHS AND RELATED TOPICS [J].

GOLUMBIC, MC .

DISCRETE MATHEMATICS, 1985, 55 (02) :113-121

[6]

KORTE N, 1987, 87461 U BONN I OP RE

[7]

KORTE N, 1985, P 11 INT WORKSH GRAP, P143

[8]

MOHRING RH, 1985, GRAPHS ORDER, P41

[9]

Rose D. J., 1976, SIAM Journal on Computing, V5, P266, DOI 10.1137/0205021

[10] SIMPLE LINEAR-TIME ALGORITHMS TO TEST CHORDALITY OF GRAPHS, TEST ACYCLICITY OF HYPERGRAPHS, AND SELECTIVELY REDUCE ACYCLIC HYPERGRAPHS [J].

TARJAN, RE ;

YANNAKAKIS, M .

SIAM JOURNAL ON COMPUTING, 1984, 13 (03) :566-579

← 1 2 →