descriptionPublicationkeyboard_double_arrow_right Article 01 Jul 2009 English Publisher:Elsevier BVJournal:Discrete Mathematics, volume 309, pages 4,653-4,655 (issn: 0012-365X,

Authors: Friedrich Regen; Christian Löwenstein; Dieter Rautenbach;

doi: 10.1016/j.disc.2009.01.012

On spanning tree congestion

- Summary
- Subjects
- Metrics

Abstract

AbstractWe 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 n32 edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219–226).

Related Organizations

Ilmenau University of Technology
Germany
Institut für Mathematik
Germany
TU Ilmenau
Germany

Keywords

Cutwidth, Layout, Congestion, Discrete Mathematics and Combinatorics, Gomory–Hu tree, Edge cut, Embedding, Theoretical Computer Science

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	8
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%

Found an issue? Give us feedback

Average

Top 10%

hybrid

Fields of Science (3) View all

Fields of Science