Unilateral Orientation of Mixed Graphs

摘要

A digraph D is unilateral if for every pair x, y of its vertices there exists a directed path from x to y, or a directed path from y to x, or both. A mixed graph M = (V,A,E) with arc-set A and edge-set E accepts a unilateral orientation, if its edges can be oriented so that the resulting digraph is unilateral. In this paper, we present the first linear-time recognition algorithm for unilaterally orientable mixed graphs. Based on this algorithm we derive a polynomial algorithm for testing whether a unilaterally orientable mixed graph has a unique unilateral orientation.