Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
Interval Graphs, Joyce C. Yang
Interval Graphs, Joyce C. Yang
HMC Senior Theses
We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The …