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

DOI10.1016/0166-218X(95)00068-3zbMath0872.05029MaRDI QIDQ1923614

Satoru Fujishige, Toshio Nemoto, Kazutoshi Ando

Publication date: 25 September 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

decompositionstrong connectivitybidirected graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Block triangularization of skew-symmetric matrices, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Making bidirected graphs strongly connected, On structures of bisubmodular polyhedra, Signed ring families and signed posets, Bisubmodular polyhedra, simplicial divisions, and discrete convexity, Parametric bisubmodular function minimization and its associated signed ring family

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pseudomatroids
• Principal structures of submodular systems
• Erratum to: T. Zaslavsky, signed graphs
• Orientation of signed graphs
• Submodular functions and optimization
• Signed posets
• On structures of bisubmodular polyhedra
• Use of matroid theory in operations research, circuits and systems theory
• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Depth-First Search and Linear Graph Algorithms