Name
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 uv∈E(G). The bandwidth of G, denoted b(G), is the minimum bandwidth over all embeddings γ, b(G)=minγ{max{|γ(u)−γ(v)|:uv∈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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.disc.2012.03.006 | Discrete Mathematics |
Keywords | Field | DocType |
Bandwidth,Tree,Polynomial time algorithm | Discrete mathematics,Graph,Combinatorics,Bandwidth (signal processing),Time complexity,Mathematics,Computation | Journal |
Volume | Issue | ISSN |
312 | 12 | 0012-365X |
Citations | PageRank | References |
0 | 0.34 | 2 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Bilinski | 1 | 12 | 1.47 |
| Kwang Ju Choi | 2 | 0 | 0.34 |
| Deborah Chun | 3 | 4 | 3.52 |
| Guoli Ding | 4 | 444 | 51.58 |
| Stan Dziobiak | 5 | 3 | 2.14 |
| Rodrigo Farnham | 6 | 0 | 0.34 |
| Perry Iverson | 7 | 12 | 1.72 |
| Shirley Leu | 8 | 0 | 0.34 |
| Lisa Warshauer Lowrance | 9 | 0 | 0.34 |