Decomposition of a bidirected graph into strongly connected components and its signed poset structure
type: Item
instance of: scholarly article
title: Decomposition of a bidirected graph into strongly connected components and its signed poset structure
zbMATH Open document ID: 0872.05029
DOI: 10.1016/0166-218X(95)00068-3
author: Kazutoshi Ando
author: Satoru Fujishige
author: Toshio Nemoto
published in: Discrete Applied Mathematics
publication date: 1997-09-25T00:00:00Z
full work available at URL: dam
review text: 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.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 933124
zbMATH Keywords: bidirected graph
zbMATH Keywords: decomposition
zbMATH Keywords: strong connectivity
reviewed by: Zhicheng Gao
MaRDI profile type: Publication
cites work: Q4773298
cites work: On structures of bisubmodular polyhedra
cites work: BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
cites work: Q4770409
cites work: Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
cites work: Pseudomatroids
cites work: Q3266932
cites work: Principal structures of submodular systems
cites work: Submodular functions and optimization
cites work: Use of matroid theory in operations research, circuits and systems theory
cites work: Signed posets
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Erratum to: T. Zaslavsky, signed graphs
cites work: Orientation of signed graphs
description: scientific article; zbMATH DE number 933124