Tree-visibility orders

被引：2

作者：

Kratsch, D

Rampon, JX

机构：

[1] Univ Jena, Fak Math & Informat, D-07740 Jena, Germany

[2] ECN, IRCYN, UMR CNRS 6597, F-44321 Nantes 3, France

来源：

DISCRETE MATHEMATICS | 1998年 / 190卷 / 1-3期

关键词：

D O I：

10.1016/S0012-365X(98)00041-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We introduce a new class of partially ordered sets, called tree-visibility orders, containing interval orders, duals of generalized interval orders and height one orders. We give a characterization of tree-visibility orders by an infinite family of minimal forbidden suborders. Furthermore, we present an efficient recognition algorithm for tree-visibility orders. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：163 / 175

页数：13

共 10 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BOGART KP, 1994, LECT NOTES COMPUTER, V831, P13

[3]

Bondy J.A., 1976, Graph Theory, V290

[4] THE COMMUNICATION COMPLEXITY OF INTERVAL ORDERS [J].

FAIGLE, U ;

SCHRADER, R ;

TURAN, G .

DISCRETE APPLIED MATHEMATICS, 1992, 40 (01) :19-28

[5]

GARBE R, 1994, THESIS U TWENTE

[6]

Gavril F., 1974, Journal of Combinatorial Theory, Series B, V16, P47, DOI 10.1016/0095-8956(74)90094-X

[7] GRAPH SANDWICH PROBLEMS [J].

GOLUMBIC, MC ;

KAPLAN, H ;

SHAMIR, R .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1995, 19 (03) :449-473

[8]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[9] Partial orders and their convex subsets [J].

Muller, H ;

Rampon, JX .

DISCRETE MATHEMATICS, 1997, 165 :507-517

[10]

Trotter W.T., 1992, COMBINATORICS PARTIA

← 1 →