Premium
Deferred‐query: An efficient approach for some problems on interval graphs
Author(s) -
Chang MawShang,
Peng ShengLung,
Liaw JennLiang
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199908)34:1<1::aid-net1>3.0.co;2-c
Subject(s) - hamiltonian path , interval graph , combinatorics , partition (number theory) , mathematics , indifference graph , discrete mathematics , interval (graph theory) , matching (statistics) , binary logarithm , graph , algorithm , computer science , chordal graph , 1 planar graph , statistics
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