Publication details for Dr George MertziosMertzios, G.B. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters 21(4): 332-337.
- Publication type: Journal Article
- ISSN/ISBN: 0893-9659
- DOI: 10.1016/j.aml.2007.04.001
- Keywords: Interval graph, Proper interval graph, Matrix representation, Matrix characterization.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
In this work a matrix representation that characterizes the interval and proper interval graphs is presented, which is useful for the efficient formulation and solution of optimization problems, such as the k-cluster problem. For the construction of this matrix representation every such graph is associated with a node versus node zero–one matrix. In contrast to representations used in most of the previous work, the proposed matrix characterization does not make use of the maximal cliques in the graph investigated.