کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950940 | 1441045 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Simple DFS on the complement of a graph and on partially complemented digraphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
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 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 GË, depth-first search (DFS) on G can be performed in O(n+mË) time, where n is the number of vertices and mË is the number of edges in 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+mË) algorithm that requires no such data-structures.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 117, January 2017, Pages 35-39
Journal: Information Processing Letters - Volume 117, January 2017, Pages 35-39
نویسندگان
Benson Joeris, Nathan Lindzey, Ross M. McConnell, Nissa Osheim,