2006 | OriginalPaper | Chapter
Acyclic Bidirected and Skew-Symmetric Graphs: Algorithms and Structure
Author : Maxim A. Babenko
Published in: Computer Science – Theory and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
weakly acyclic
bidirected graph we mean such a graph having no simple cycles. We call a bidirected graph
strongly acyclic
if it has no cycles (even non-simple). 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). We use the notion of
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.