TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1990

COGA 5-Wheel

Page Content

to Navigation

Preprints 1990

Orthogonal Structures in Directed Graphs
Citation key Report-255-1990
Author Stefan Felsner
Pages 309-321
Year 1990
Journal Journal of Combinatorial Theory, Series B, 1993
Volume 57
Number 255
Institution Technische Universität Berlin, Institut für Mathematik
Abstract Using the minimal cost flow algorithm of Ford and Fulkerson and the notion of orthogonality between chain and antichain families András Frank could give common access (and proof) to some famous results in the theory of finite posets: 1.\ Theorem of Greene and Kleitman, 2.\ Theorem of Greene, 3.\ the $t$-phenomenon, 4.\ the conjugacy of the partitions associated with the $k$ antichain and ℓ chain families. Some new insight into the behaviour of the minimum cost flow algorithm on the special networks associated with posets and digraphs enables us to exhibit orthogonal structures in arbitrary digraphs. The role of $k$ antichain families is taken by families of $k$ disjoint $1$–weightings, a family of disjoint pathes and cycles including ℓ pathes takes care of the role of ℓ chain families. We then show how the orthogonal structures can be used to generalize the Greene Kleitman theory to acyclic directed graphs and partly even to arbitrary directed graphs.
Bibtex Type of Publication Preprint
Download Bibtex entry


Quick Access

Schnellnavigation zur Seite über Nummerneingabe