Deferred-query: An efficient approach for some problems on interval graphs
Maw‐Shang Chang, Sheng‐Lung Peng, Jenn‐Liang Liaw · Networks · 1999
This paper introduces the idea of a deferred-query approach to design O(n) algorithms for the domatic partition, optimal path cover, Hamiltonian path, Hamiltonian circuit, and maximum matching problems on interval graphs given n endpoint-sorted intervals. The previous best-known algorithms run in O(n log log n) or O(n +m) time, where m is the number of edges in the corresponding interval graphs. © 1999 John Wiley & Sons, Inc. Networks 34: 1–10, 1999