A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs

摘要

We present a fully dynamic graph algorithm to recognize proper interval graphs that runs in O(log n) worst case time per edge update, where n is the number of vertices in the graph. The algorithm also maintains the connected components and supports connectivity queries in O(log n) time.