Author/Authors :
Bilinski، نويسنده , , Mark and Choi، نويسنده , , Kwang Ju and Chun، نويسنده , , Deborah and Ding، نويسنده , , Guoli and Dziobiak، نويسنده , , Stan and Farnham، نويسنده , , Rodrigo and Iverson، نويسنده , , Perry and Leu، نويسنده , , Shirley and Lowrance، نويسنده , , Lisa Warshauer، نويسنده ,
Abstract :
For a graph G , let γ : V ( G ) → { 1 , … , | V ( G ) | } be a one-to-one function. The bandwidth of γ is the maximum of | γ ( u ) − γ ( v ) | over u v ∈ E ( G ) . The bandwidth of G , denoted b ( G ) , is the minimum bandwidth over all embeddings γ , b ( G ) = min γ { max { | γ ( u ) − γ ( v ) | : u v ∈ E ( G ) } } . In this paper, we show that the bandwidth computation problem for trees of diameter at most 4 can be solved in polynomial time. This naturally complements the result computing the bandwidth for 2-caterpillars.
