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
    FAIGLE, U
    SCHRADER, R
    TURAN, G
    [J]. 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
    GOLUMBIC, MC
    KAPLAN, H
    SHAMIR, R
    [J]. 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
    Muller, H
    Rampon, JX
    [J]. DISCRETE MATHEMATICS, 1997, 165 : 507 - 517
  • [10] Trotter W.T., 1992, COMBINATORICS PARTIA
1