Geodesic
A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph
Canadian journal of mathematics, Tome 27 (1975) no. 2, pp. 348-351

Voir la notice de l'article provenant de la source Cambridge University Press

As an analog of a recently established minimax equality for directed graphs [1], I. Simon has suggested that the following be investigated.1.1. For a finite acyclic directed graph G, a minimum collection of directed coboundaries whose union is the edge set of G has cardinality equal to that of a maximum strong matching of G.This minimax equality is here proved, using a characterization of a maximum strong matching of an acyclic graph as the set of edges of a longest directed path in the graph.The terms employed in the above theorem are defined as follows. Let G be a finite directed graph with vertex set VG and edge set eG 
Vidyasankar, K.; Younger, D. H. A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph. Canadian journal of mathematics, Tome 27 (1975) no. 2, pp. 348-351. doi: 10.4153/CJM-1975-042-7
@article{10_4153_CJM_1975_042_7,
     author = {Vidyasankar, K. and Younger, D. H.},
     title = {A {Minimax} {Equality} {Related} to the {Longest} {Directed} {Path} in an {Acyclic} {Graph}},
     journal = {Canadian journal of mathematics},
     pages = {348--351},
     year = {1975},
     volume = {27},
     number = {2},
     doi = {10.4153/CJM-1975-042-7},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-042-7/}
}
TY  - JOUR
AU  - Vidyasankar, K.
AU  - Younger, D. H.
TI  - A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph
JO  - Canadian journal of mathematics
PY  - 1975
SP  - 348
EP  - 351
VL  - 27
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-042-7/
DO  - 10.4153/CJM-1975-042-7
ID  - 10_4153_CJM_1975_042_7
ER  - 
%0 Journal Article
%A Vidyasankar, K.
%A Younger, D. H.
%T A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph
%J Canadian journal of mathematics
%D 1975
%P 348-351
%V 27
%N 2
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1975-042-7/
%R 10.4153/CJM-1975-042-7
%F 10_4153_CJM_1975_042_7

[1] 1. Lucchesi, C. L. and Younger, D. H., A minimax theorem for directed graphs (to appear). Google Scholar

Cité par Sources :