Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

DOI10.1007/11753728_6MaRDI QIDQ3434679zbMATH OpenOpenAlexFDO

Authors Maxim Babenko

Publication date 2 May 2007

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0607547

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: emph{Bidirected graphs} (a sort of nonstandard graphs introduced by Edmonds and Johnson) provide a natural generalization to the notions of directed and undirected graphs. By a emph{weakly (node- or edge-) acyclic} bidirected graph we mean such graph having no (node- or edge-) simple cycles. We call a bidirected graph emph{strongly acyclic} if it has no cycles (even non-simple). Unlike the case of standard graphs, a bidirected graph may be weakly acyclic but still have non-simple cycles. Testing a given bidirected graph for weak acyclicity is a challenging combinatorial problem, which also has a number of applications (e.g. checking a perfect matching in a general graph for uniqueness). We present (generalizing results of Gabow, Kaplan, and Tarjan) a modification of the depth-first search algorithm that checks (in linear time) if a given bidirected graph is weakly acyclic (in case of negative answer a simple cycle is constructed). Our results are best described in terms of emph{skew-symmetric graphs} (the latter give another, somewhat more convenient graph language which is essentially equivalent to the language of bidirected graphs). We also give structural results for the class of weakly acyclic bidirected and skew-symmetric graphs explaining how one can construct any such graph starting from strongly acyclic instances and, vice versa, how one can decompose a weakly acyclic graph into strongly acyclic ``parts. Finally, we extend acyclicity test to build (in linear time) such a decomposition.

Recommendations

• Minimum mean cycle problem in bidirected and skew-symmetric graphs
• Decomposition of a bidirected graph into strongly connected components and its signed poset structure
• On flows in simple bidirected and skew-symmetric networks
• Path problems in skew-symmetric graphs
• Transitive closure and transitive reduction in bidirected graphs

Cited in

(3)

• Decomposition of a bidirected graph into strongly connected components and its signed poset structure
• Making bidirected graphs strongly connected
• On flows in simple bidirected and skew-symmetric networks

This page was built for publication: Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3434679)