Dynamic representation of consecutive-ones matrices and interval graphs
Date
2015
Authors
Springer, William M., II, author
McConnell, Ross M., advisor
Ray, Indrajit, committee member
Bohm, Wim, committee member
Hulpke, Alexander, committee member
Journal Title
Journal ISSN
Volume Title
Abstract
We give an algorithm for updating a consecutive-ones ordering of a consecutive-ones matrix when a row or column is added or deleted. When the addition of the row or column would result in a matrix that does not have the consecutive-ones property, we return a well-known minimal forbidden submatrix for the consecutive-ones property, known as a Tucker submatrix, which serves as a certificate of correctness of the output in this case, in O(n log n) time. The ability to return such a certificate within this time bound is one of the new contributions of this work. Using this result, we obtain an O(n) algorithm for updating an interval model of an interval graph when an edge or vertex is added or deleted. This matches the bounds obtained by a previous dynamic interval-graph recognition algorithm due to Crespelle. We improve on Crespelle's result by producing an easy-to-check certificate, known as a Lekkerkerker-Boland subgraph, when a proposed change to the graph results in a graph that is not an interval graph. Our algorithm takes O(n log n) time to produce this certificate. The ability to return such a certificate within this time bound is the second main contribution of this work.
Description
Rights Access
Subject
certifying algorithm
interval graph
Tucker matrix
consecutive-ones matrix
asteroidal triple
Lekkerkerker-Boland