To guarantee quality of service (QoS), the requirements for video transmission, such as delay and cell loss rate (CLR), are very stringent. These constraints are difficult to meet if high network utilization is desired. In this paper, dynamic bandwidth allocation algorithms are proposed to improve the bandwidth utilization. The first approach based on scene change identification, in which the bandwidth is allocated based on the maximum and mean bandwidth of the scene, is applicable to delivering pre-recorded videos. The second approach, in which the bandwidth is adjusted based on the current frame size, is on-line and can be used to deliver real-time videos on-line. When the bandwidth deviation is large enough, the bandwidth renegotiation process is triggered. Compared with CBR service, network utilization can be improved significantly for the same CLR. In general, to achieve a very low CLR and high bandwidth utilization, the renegotiation frequency may become high. Algorithms, which are proven to be effective in reducing the renegotiation frequency while keeping the bandwidth utilization at a reasonable level, are also proposed.