Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649687 | Discrete Mathematics | 2008 | 9 Pages |
Abstract
This paper investigates the problem of embedding a graph into a tree with the same vertex set (a spanning tree in particular), such that the maximum congestion of the edges is minimized. We calculate exact formulas for the tree congestion and spanning tree congestion for various families of graphs, including grids and complete bipartite graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Stephen W. Hruska,