Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

Details Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure

2006-07-21

arxiv.org/abs/math/0607547v1

Mathematics

Combinatorics

22 pages, 11 pictures, CSR 2006

Scientific paper

\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.

Affiliated with

Also associated with

No associations

Rating

Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-169877