Ultra-dense network (UDN) is considered as a promising technology in 5G wireless networks. In an UDN network, dynamic traffic patterns can lead to a high computational complexity and an excessive communications overhead with traditional resource allocation schemes. In this paper, a new resource allocation scheme presenting a low computational overhead and a low subband handoff rate in a dynamic ultra-dense heterogeneous network is presented. The scheme first defines a new interference estimation method that constructs network interference state map, based on which a radio resource allocation scheme is proposed. The resource allocation problem is a MAX-K cut problem and can be solved through a graph-theoretical approach. System level simulations reveal that the proposed scheme decreases the subband handoff rate by 30% with less than 3.2% network throughput degradation.