Decomposition of a bidirected graph into strongly connected components and its signed poset structure

摘要

A bidirected graph is a graph each arc of which has either two positive end-vertices (tails), two negative end-vertices (heads), or one positive end-vertex (a tail) and one negative end-vertex (a head). We define the strong connectivity of a bidirected graph as a generalization of the strong connectivity of an ordinary directed graph. We show that a bidirected graph is decomposed into strongly connected components and that a signed poset structure is naturally defined on the set of the consistent strongly connected components. We also give a linear time algorithm for decomposing a bidirected graph into strongly connected components. Furthermore, we discuss the relationship between the decomposition of a bidirected graph and the minimization of a certain bisubmodular function.