How to make a digraph strongly connected |
| |
| Authors: | András Frank |
| |
| Institution: | (1) Research Institute for Telecommunication, Gábor á. u. 65, H-1026 Budapest, Hungary;(2) JATE Bolyai Institute, H-6720 Szeged, Hungary |
| |
| Abstract: | Given a directed graphG, acovering is a subsetB of edges which meets all directed cuts ofG. Equivalently, the contraction of the elements ofB makesG strongly connected. AnO(n
5) primal-dual algorithm is presented for finding a minimum weight covering of an edge-weighted digraph. The algorithm also
provides a constructive proof for a min-max theorem due to Lucchesi and Younger and for its weighted version. |
| |
| Keywords: | 05 C 20 90 C 10 05 C 40 68 C 25 68 E 10 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
