A matrix characterization of interval and proper interval graphs

Mertzios, G.B.

doi:10.1016/j.aml.2007.04.001

A matrix characterization of interval and proper interval graphs

Mertzios, G.B.

Authors

Dr George Mertzios george.mertzios@durham.ac.uk
Associate Professor

Abstract

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.

Citation

Mertzios, G. (2008). A matrix characterization of interval and proper interval graphs. Applied Mathematics Letters, 21(4), 332-337. https://doi.org/10.1016/j.aml.2007.04.001

Journal Article Type	Article
Publication Date	Apr 1, 2008
Deposit Date	Dec 8, 2011
Journal	Applied Mathematics Letters
Print ISSN	0893-9659
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	21
Issue	4
Pages	332-337
DOI	https://doi.org/10.1016/j.aml.2007.04.001
Keywords	Interval graph, Proper interval graph, Matrix representation, Matrix characterization.