On tree congestion of graphs |
| |
Authors: | Stephen W Hruska |
| |
Institution: | Mathematics Department, University of Wisconsin-Madison, 480 Lincoln Dr, Madison, WI 53706, USA |
| |
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: | Graph Tree congestion Spanning tree congestion Complete bipartite Grid |
本文献已被 ScienceDirect 等数据库收录! |
|