Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00123
A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
Grant A. Cheston and
Tjoen Seng Jap
Vol. 10, no. 2, pp. 159-190, 2006. Survey paper.
Abstract Three classes of graphs, simplicial, upper bound, and middle
graphs, have been known for some time, but many of their algorithmic
properties have not been published. The definitions for these graph
classes are reviewed, and their
relationships with other common graph classes (especially line
and perfect graphs) are presented. Efficient algorithms are
referenced or outlined to recognize each class of graphs.
Finally, for each class of graphs and most of the common
parameters of graphs, either an algorithm or an NP-complete
result is presented, or it is referenced in the literature.
|
Journal Supporters
|