The complexity of the partial order dimension problem. (English) Zbl 0516.06001
References:
| [1] | Set-packing and threshold graphsRes. reportCORR 73-21Univ. WaterlooWaterloo, Ontario, Canada1973 |
| [2] | Chvátal, Václav; Hammer, PeterL., Aggregation of inequalities in integer programming, Studies in integer programming (Proc. Workshop, Bonn, 1975), (1977), North-Holland, Amsterdam · Zbl 0384.90091 |
| [3] | Ph.D. ThesisHigher and multi-dimensional analogues of interval graphsRutgers UniversityNew Brunswick, NJ1981 |
| [4] | Dushnik, Ben; Miller, E. W., Partially ordered sets, Amer. J. Math., 63, 600, (1941) · Zbl 0025.31002 |
| [5] | Fishburn, PeterC., Intransitive indifference with unequal indifference intervals, J. Mathematical Psychology, 7, 144, (1970) · Zbl 0191.31501 |
| [6] | Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039 |
| [7] | Garey, M. R.; Johnson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237, (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 |
| [8] | Golumbic, MartinCharles, Algorithmic graph theory and perfect graphs, (1980) · Zbl 0541.05054 |
| [9] | Hiraguchi, Toshio, On the dimension of partially ordered sets, Sci. Rep. Kanazawa Univ., 1, 77, (1951) · Zbl 0200.00013 |
| [10] | Ibaraki, T.; Peled, U. N., Sufficient conditions for graphs to have threshold number 2, Studies on graphs and discrete programming (Brussels, 1979), 11, 241, (1981), North-Holland, Amsterdam · Zbl 0479.05058 |
| [11] | Kelly, David, The 3-irreducible partially ordered sets, Canad. J. Math., 29, 367, (1977) · Zbl 0357.06004 |
| [12] | Ph.D. ThesisExtremal problems in dimension theory for partially ordered setsMassachusetts Institute of TechnologyCambridge1973 |
| [13] | private communication · Zbl 1207.68077 |
| [14] | Ore, Oystein, Theory of graphs, (1962) · Zbl 0105.35401 |
| [15] | Pnueli, A.; Lempel, A.; Even, S., Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23, 160, (1971) · Zbl 0204.24604 |
| [16] | Roberts, FredS.; Tutte, W. T., On the boxicity and cubicity of a graph, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), 301, (1969), Academic Press, New York · Zbl 0193.24301 |
| [17] | Trotter, W. T.; Bogart, K. P., On the complexity of posets, Discrete Math., 16, 71, (1976) · Zbl 0351.06003 · doi:10.1016/0012-365X(76)90095-9 |
| [18] | Trotter, Jr., WilliamT.; Moore, Jr., JohnI., Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math., 16, 361, (1976) · Zbl 0356.06007 |
| [19] | Yannakakis, Mihalis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods, 2, 77, (1981) · Zbl 0496.68033 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
