ZIB

Treffer pro Seite

Treffer 1 - 1 | 1 Treffer

Sortierung

Digitale Medien

Branchings in rooted graphs and the diameter of greedoids (1988)

Ziegler, G. M.

Springer

Combinatorica 8 (1988), S. 217-234

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1439-6912

Schlagwort(e): 05 B 35 ; 05 c 20 ; 68 Q 20

Quelle: Springer Online Journal Archives 1860-2000

Thema: Mathematik

Notizen: Abstract LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr 2−r+1 (r〉0). This answers a question by L. Lovász. There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr. Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2r−1.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1007/BF02122803

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Treffer 1 - 1 | 1 Treffer