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

DOI10.1016/j.ipl.2016.08.006zbMath1388.68232arXiv1311.1859OpenAlexW2962745257MaRDI QIDQ318918

Nathan Lindzey, Ross M. McConnell, Nissa Osheim, Benson L. 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

graph algorithmsdepth-first searchgraph traversalpartially complemented digraphs

Mathematics Subject Classification ID

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

Related Items (1)

Speeding up Graph Algorithms via Switching Classes

Cites Work

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

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