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

DOI10.1016/J.IPL.2016.08.006zbMATH Open1388.68232arXiv1311.1859OpenAlexW2962745257MaRDI QIDQ318918FDOQ318918

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)

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.

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

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

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)

Cites Work

• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Depth-First Search and Linear Graph Algorithms
• Modular decomposition and transitive orientation
• Title not available (Why is that?)
• Transitiv orientierbare Graphen
• Simple efficient graph compression schemes for dense and complement graphs
• An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
• Title not available (Why is that?)

Cited In (2)

• Title not available (Why is that?)
• 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)