SIAM Journal on Discrete Mathematics · 1999 · 10 citations · 15 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsGraph AlgorithmsGraph LabelingGraph TheoryComputational Complexity Of Graph AlgorithmsDifference LabelingEdge-diameter
The edge-bandwidth of a graph is the minimum, over all labelings of the edges with distinct integers, of the maximum difference between labels of two incident edges. We prove that edge-bandwidth is at least as large as bandwidth for every graph, with equality for certain caterpillars. We obtain sharp or nearly sharp bounds on the change in edge-bandwidth under addition, subdivision, or contraction of edges. We compute edge-bandwidth for Kn, Kn,n, caterpillars, and some theta graphs.
15
The NP-Completeness of the bandwidth minimization problem
Ch. H. Papadimitriou · Computing · 1976 · 409 citations
The bandwidth problem for graphs and matrices—a survey
Phyllis Zweig Chinn, Jarmila Chvátalová, A. K. Dewdney et al. · Journal of Graph Theory · 1982 · 306 citations
Complexity Results for Bandwidth Minimization
M. R. Garey, Ronald Graham, David S. Johnson et al. · SIAM Journal on Applied Mathematics · 1978 · 296 citations