×

A Fully dynamic algorithm for recognizing and representing proper interval graphs. (English) Zbl 0992.68065

Summary: We study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modification can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclusion-free family of intervals. This problem has important applications in physical mapping of DNA.
We give a near-optimal fully dynamic algorithm for this problem. It operates in \(O(\log n)\) worst-case time per edge insertion or deletion. We prove a close lower bound of \(\Omega(\log n/(\log\log n+\log b))\) amortized time per operation in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each edge operation in \(O(1)\) time. As a byproduct of our algorithm, we solve in \(O(\log n)\) worst-case time the problem of maintaining connectivity in a dynamically changing proper interval graph.

MSC:

68Q25 Analysis of algorithms and problem complexity
68W40 Analysis of algorithms
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI