Strongly connected orientations of mixed multigraphs

Fan R.K. Chung, Michael R. Garey, Robert E. Tarjan

Research output: Contribution to journalArticle

54 Scopus citations

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 42 + Ar. The proof gives a polynomial‐time algorithm for constructing such an orientation.

Original languageEnglish (US)
Pages (from-to)477-484
Number of pages8
JournalNetworks
Volume15
Issue number4
DOIs
StatePublished - Jan 1 1985
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Strongly connected orientations of mixed multigraphs'. Together they form a unique fingerprint.

  • Cite this