Article ID Journal Published Year Pages File Type
4649687 Discrete Mathematics 2008 9 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,