On spanning tree congestion |
| |
Authors: | Christian Lö wenstein,Friedrich Regen |
| |
Affiliation: | Institut für Mathematik, TU Ilmenau, Postfach 100565, D-98684 Ilmenau, Germany |
| |
Abstract: | We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge cut defined in G by the vertex sets of the two components of T−e contains at most edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226). |
| |
Keywords: | Congestion Edge cut Cutwidth Gomory-Hu tree Layout Embedding |
本文献已被 ScienceDirect 等数据库收录! |