Premium
Strongly connected orientations of mixed multigraphs
Author(s) -
Chung Fan R. K.,
Garey Michael R.,
Tarjan Robert E.
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150409
Subject(s) - multigraph , reachability , orientation (vector space) , mathematics , undirected graph , combinatorics , graph , strongly connected component , mixed graph , time complexity , directed graph , line graph , geometry , voltage graph
Abstract We study the problem of orienting all the undirected edges of a mixed multigraph so as to preserve reachability. Extending work by Robbins and by Boesch and Tindell, we develop a linear‐time algorithm to test whether there is an orientation that preserves strong connectivity and to construct such an orientation whenever possible. This algorithm makes no attempt to minimize distances in the resulting directed graph, and indeed the maximum distance, for example, can blow up by a factor proportional to the number of vertices in the graph. Extending work by Chvátal and Thomassen, we then prove that, if a mixed multigraph of radius r has any strongly connected orientation, it must have an orientation of radius at most 4 2 + A r . The proof gives a polynomial‐time algorithm for constructing such an orientation.