One-Way Trail Orientations

Authors Anders Aamand , Niklas Hjuler , Jacob Holm , Eva Rotenberg



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.6.pdf
  • Filesize: 448 kB
  • 13 pages

Document Identifiers

Author Details

Anders Aamand
  • University of Copenhagen, Copenhagen, Denmark
Niklas Hjuler
  • University of Copenhagen, Copenhagen, Denmark
Jacob Holm
  • University of Copenhagen, Copenhagen, Denmark
Eva Rotenberg
  • Technical University of Denmark, Lyngby, Denmark

Cite AsGet BibTex

Anders Aamand, Niklas Hjuler, Jacob Holm, and Eva Rotenberg. One-Way Trail Orientations. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.6

Abstract

Given a graph, does there exist an orientation of the edges such that the resulting directed graph is strongly connected? Robbins' theorem [Robbins, Am. Math. Monthly, 1939] asserts that such an orientation exists if and only if the graph is 2-edge connected. A natural extension of this problem is the following: Suppose that the edges of the graph are partitioned into trails. Can the trails be oriented consistently such that the resulting directed graph is strongly connected? We show that 2-edge connectivity is again a sufficient condition and we provide a linear time algorithm for finding such an orientation. The generalised Robbins' theorem [Boesch, Am. Math. Monthly, 1980] for mixed multigraphs asserts that the undirected edges of a mixed multigraph can be oriented to make the resulting directed graph strongly connected exactly when the mixed graph is strongly connected and the underlying graph is bridgeless. We consider the natural extension where the undirected edges of a mixed multigraph are partitioned into trails. It turns out that in this case the condition of the generalised Robbin's Theorem is not sufficient. However, we show that as long as each cut either contains at least 2 undirected edges or directed edges in both directions, there exists an orientation of the trails such that the resulting directed graph is strongly connected. Moreover, if the condition is satisfied, we may start by orienting an arbitrary trail in an arbitrary direction. Using this result one obtains a very simple polynomial time algorithm for finding a strong trail orientation if it exists, both in the undirected and the mixed setting.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Paths and connectivity problems
Keywords
  • Graph algorithms
  • Robbins' theorem
  • Graph orientation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Frank Boesch and Ralph Tindell. Robbins’s theorem for mixed multigraphs. The American Mathematical Monthly, 87(9):716-719, 1980. URL: http://www.jstor.org/stable/2321858.
  2. Fan R. K. Chung, Michael R. Garey, and Robert E. Tarjan. Strongly connected orientations of mixed multigraphs. Networks, 15(4):477-484, 1985. URL: http://dx.doi.org/10.1002/net.3230150409.
  3. Jacob Holm, Eva Rotenberg, and Mikkel Thorup. Dynamic bridge-finding in Õ(log2 n) amortized time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '18, pages 35-52, 2018. URL: http://dl.acm.org/citation.cfm?id=3174304.3175269.
  4. John Hopcroft and Robert Tarjan. Algorithm 447: Efficient algorithms for graph manipulation. Commun. ACM, 16(6):372-378, 1973. URL: http://dx.doi.org/10.1145/362248.362272.
  5. Pierre Kelsen and Vijaya Ramachandran. On finding minimal 2-connected subgraphs. In Proceedings of the Second Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 28-30 January 1991, San Francisco, California., pages 178-187, 1991. URL: http://dl.acm.org/citation.cfm?id=127787.127824.
  6. Zoltán Király and Zoltán Szigeti. Simultaneous well-balanced orientations of graphs. J. Comb. Theory, Ser. B, 96(5):684-692, 2006. Google Scholar
  7. Kurt Mehlhorn, Adrian Neumann, and Jens M. Schmidt. Certifying 3-edge-connectivity. Algorithmica, 77(2):309-335, 2017. URL: http://dx.doi.org/10.1007/s00453-015-0075-x.
  8. Hiroshi Nagamochi and Toshihide Ibaraki. Algorithmic Aspects of Graph Connectivity. Cambridge University Press, New York, NY, USA, 1 edition, 2008. Google Scholar
  9. J. A. Nash-Willams. On orientations, connectivity and odd-vertex-pairings in finite graphs. Canad. J. Math., 12(5):555-567, 1960. Google Scholar
  10. H. E. Robbins. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly, 46(5):281-283, 1939. URL: http://www.jstor.org/stable/2303897.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail