COUNTING END-POINT SEQUENCES FOR INTERVAL ORDERS AND INTERVAL-GRAPHS

被引：2

作者：

BELFER, A

GOLUMBIC, MC

机构：

[1] IBM CORP, ISRAEL SCI CTR, TECHNION CITY, HAIFA, ISRAEL

[2] BAR ILAN UNIV, RAMAT GAN, ISRAEL

来源：

DISCRETE MATHEMATICS | 1993年 / 114卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(93)90353-U

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we design and analyze efficient algorithms for counting the number of endpoint sequences representing a given interval graph or interval order. The results are based on the construction of a suitable tree data structure to represent multiple solutions. We describe the relation of our methods to PQ-trees and MPQ-trees. Finally, we discuss the connection of these structures with temporary reasoning. © 1993.

引用

收藏

页码：23 / 39

页数：17

相关论文

共 18 条

[1] MAINTAINING KNOWLEDGE ABOUT TEMPORAL INTERVALS [J].

ALLEN, JF .

COMMUNICATIONS OF THE ACM, 1983, 26 (11) :832-843

[2]

[Anonymous], 1985, INTERVAL ORDERS INTE

[3]

BELFER A, 1990, 5TH P JER C INF TECH, P774

[4] ON THE TOPOLOGY OF THE GENETIC FINE STRUCTURE [J].

BENZER, S .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 1959, 45 (11) :1607-1620

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

[6] DETECTION OF STRUCTURE IN ATTITUDES AND DEVELOPMENTAL PROCESSES [J].

COOMBS, CH ;

SMITH, JEK .

PSYCHOLOGICAL REVIEW, 1973, 80 (05) :337-351

[7] INTERVAL-GRAPHS AND INTERVAL ORDERS [J].

FISHBURN, PC .

DISCRETE MATHEMATICS, 1985, 55 (02) :135-149

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

FULKERSON, DR ;

GROSS, OA .

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

[9] CHARACTERIZATION OF COMPARABILITY GRAPHS + OF INTERVAL GRAPHS [J].

GILMORE, PC ;

HOFFMAN, AJ .

CANADIAN JOURNAL OF MATHEMATICS, 1964, 16 (03) :539-&

[10]

Golumbic M. C., 1980, ALGORITHMIC GRAPH TH