Simple DFS on the complement of a graph and on partially complemented digraphs

DOI10.1016/J.IPL.2016.08.006MaRDI QIDQ318918zbMATH OpenOpenAlexFDO

Authors Nathan Lindzey, R. M. McConnell, Nissa Osheim, Benson Joeris

Publication date 6 October 2016

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

depth-first searchgraph algorithmsgraph traversalpartially complemented digraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Abstract: A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. A partially complemented digraph $widetildeG$ is a digraph obtained from a sequence of vertex complement operations on $G$. Dahlhaus et al. showed that, given an adjacency-list representation of $widetildeG$, depth-first search (DFS) on $G$ can be performed in $O(n+widetildem)$ time, where $n$ is the number of vertices and $widetildem$ is the number of edges in $widetildeG$. To achieve this bound, their algorithm makes use of a somewhat complicated stack-like data structure to simulate the recursion stack, instead of implementing it directly as a recursive algorithm. We give a recursive $O(n+widetildem)$ algorithm that uses no complicated data-structures.

Recommendations

• scientific article; zbMATH DE number 1753166
• scientific article; zbMATH DE number 1086495
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster

Cites work

• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Depth-First Search and Linear Graph Algorithms
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Modular decomposition and transitive orientation
• Simple efficient graph compression schemes for dense and complement graphs
• Transitiv orientierbare Graphen

Cited in

(2)

• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• Speeding up Graph Algorithms via Switching Classes

This page was built for publication: Simple DFS on the complement of a graph and on partially complemented digraphs

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