Premium
Using an interval graph approach to efficiently solve the housing benefit data retrieval problem
Author(s) -
Vasko Francis J.,
Kunkel Jeffrey D.,
Gorman Patrick
Publication year - 2011
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2010.00803.x
Subject(s) - interval graph , clique , computer science , graph , interval (graph theory) , greedy algorithm , cover (algebra) , interval data , mathematical optimization , algorithm , mathematics , theoretical computer science , combinatorics , data mining , line graph , pathwidth , mechanical engineering , engineering , measure (data warehouse)
Rappos and Thompson use a set covering formulation and a commercial software package to solve the problem of trying to minimize the number of data sets that have to be read in retrieving all new housing benefit (HB) data entries for a fixed period of time. In this paper, we show that determining the minimum number of data sets that have to be read in retrieving all new HB data entries for a fixed period of time can be solved by finding a minimum size clique cover for an interval graph. Since it is well‐known that a greedy algorithm finds a guaranteed minimum size clique cover for an interval graph, this approach will be more efficient than a set covering approach. Finally, it is obvious that this interval graph formulation and greedy algorithm solution approach is applicable to other data retrieval problems.