Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-26T01:25:22.074Z Has data issue: false hasContentIssue false
  • English
  • Français

A Minimax Equality Related to the Longest Directed Path in an Acyclic Graph

Published online by Cambridge University Press:  20 November 2018

K. Vidyasankar  and
D. H. Younger
K. Vidyasankar
Affiliation:
University of Waterloo, Waterloo, Ontario
D. H. Younger
Affiliation:
University of Waterloo, Waterloo, Ontario
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 27 , Issue 2 , 01 April 1975 , pp. 348 - 351
Copyright
Copyright © Canadian Mathematical Society 1975

References

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