Title of article :
Orthogonal Structures in Directed Graphs
Author/Authors :
Felsner، نويسنده , , S.، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 1993
Pages :
13
From page :
309
To page :
321
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 l 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 l-weightings, a family of disjoint paths and cycles including l paths takes care of the role of l 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.
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
1993
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1525730
Link To Document :
بازگشت