On the Representation of a PI-Graph
Abstract
Full Text:
PDF (Português (Brasil))References
[1] K.S. Booth, G.S. Lueker, Testing for the consecutive ones property, interval graphs, and planarity using PQ-tree algorithms, J. Comput. System Sci., 13 (1976), 335-379.
A. Brandst¨adt, V. Le, J. Spinrad, “Graph Classes - a Survey”, SIAM, Monographs on Discrete Mathematics and Applications, 1999.
F. Cheah, “A Recognition Algorithm for II-Graphs”, Doctoral Thesis, TR246/90, Dept. of Computer Science, Univ. of Toronto, 1990.
F. Cheah, D.G. Corneil, On the structure of trapezoid graphs, Discrete Appied Mathematics, 66 (1996), 109-133.
O. Cogis, On the Ferrers dimension of a digraph, Discrete Math., 38 (1982), 47-52.
D.J. Corneil, P.A. Kamula. Extensions of permutation and interval graphs, Congressus Numerantium, 58 (1987), 267–275.
S. Even, A. Pnueli, A. Lempel, Permutation graphs and transitive graphs, J. ACM., 19 (1972), 400-410.
S. Felsner. Tolerance graphs and orders, Lecture Notes in Computer Science 657 (1992), 17–26.
M.C. Golumbic, “Algorithmic Graph Theory and Perfect Graphs”, Academic Press, New York, 1980.
M. Habib, R.H. M¨ohring, “Recognition of Partial Orders with Interval Dimension Two Via Transitive Orientation with Side Constrains”, Technical Report, TR 244/90, Tu Berlin, 1990.
M. Habib, R. McConnell, C. Paul, L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, 234 (2000), 59-84.
G. Haj´os, ¨ Uber eine art von graphen, Internat. Math. Nachr., 11 (1957), problem 65.
N. Korte, H. M¨ohring, An incremental linear-time algorithm for recognizing interval graphs, SIAM J. Comput., 18 (1989), 68-81.
Y-L Lin, Triangle graphs and simple trapezoid graphs, Journal of Information Science and Engineering, 18 (2002), 467-473.
T.H. Ma, “Algorithms on Special Classes of Graphs and Partially Ordered Sets”, Ph.D. Thesis, Dept. of Computer Science, Vanderbilt Univ., Nashville, TN, 1990.
A. Pnueli, A. Lempel, S. Even, Transitive orientation of graphs and identification of permutation graphs, Canad. J. Math., 23 (1971), 160-175.
DOI: https://doi.org/10.5540/tema.2007.08.01.0001
Article Metrics
Metrics powered by PLOS ALM
Refbacks
- There are currently no refbacks.
Trends in Computational and Applied Mathematics
A publication of the Brazilian Society of Applied and Computational Mathematics (SBMAC)
Indexed in: