Decomposition of a bidirected graph into strongly connected components and its signed poset structure (Q1923614)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Decomposition of a bidirected graph into strongly connected components and its signed poset structure |
scientific article |
Statements
Decomposition of a bidirected graph into strongly connected components and its signed poset structure (English)
0 references
25 September 1997
0 references
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.
0 references
bidirected graph
0 references
decomposition
0 references
strong connectivity
0 references