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

详细信息    查看全文

• 作者：Benson Joeris^a ; Nathan Lindzey^b ; ^{nlindzey@uwaterloo.ca" class="auth_mail" title="E-mail the corresponding author} ; Ross M. McConnell^c ; Nissa Osheim^c
• 关键词：Depth-first search ; Graph algorithms ; Graph traversal ; Partially complemented digraphs
• 刊名：Information Processing Letters
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：117
• 期：Complete
• 页码：35-39
• 全文大小：251 K

文摘

A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. Given a digraph G, a partially complemented digraph  928e65065bdad0e56a2c">$\tilde{G}$ is a digraph obtained from G by performing a sequence of vertex complement operations on G  . Dahlhaus et al. showed that, given an adjacency-list representation of 928e65065bdad0e56a2c">$\tilde{G}$, depth-first search (DFS) on G   can be performed in $O(n+\tilde{m})$ time, where n   is the number of vertices and $\tilde{m}$ is the number of edges in 928e65065bdad0e56a2c">$\tilde{G}$. This can be used for finding a depth-first spanning forest and the strongly connected components of the complement of G in time that is linear in the size of G  , and Dahlhaus et al. give applications to finding the modular decomposition of an undirected graph that require that some adjacency lists be complemented and others not. 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+\tilde{m})$ algorithm that requires no such data-structures.