Simple DFS on the complement of a graph and on partially complemented digraphs
详细信息 查看全文
- 作者：Benson Joerisa ; Nathan Lindzeyb ; nlindzey@uwaterloo.ca" class="auth_mail" title="E-mail the corresponding author ; Ross M. McConnellc ; Nissa Osheimc
- 关键词：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 
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 , depth-first search (DFS) on G can be performed in time, where n is the number of vertices and is the number of edges in . 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 algorithm that requires no such data-structures.
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 , depth-first search (DFS) on G can be performed in time, where n is the number of vertices and is the number of edges in . 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 algorithm that requires no such data-structures.