查看文章

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