Partially complemented representations of digraphsReportar como inadecuado

Partially complemented representations of digraphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Department. of Computer Science Cologne 2 RESEDAS - Software Tools for Telecommunications and Distributed Systems INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications 3 Computer Science Department, Colorado State University

Abstract : A complementation operation on a vertex of a digraph changes all outgoing arcs into non-arcs, and outgoing non-arcs into arcs. This defines an equivalence relation where two digraphs are equivalent if one can be obtained from the other by a sequence of such operations. We show that given an adjacency-list representation of a digraph G, many fundamental graph algorithms can be carried out on any member G- of G-s equivalence class in On+m time, where m is the number of arcs in G, not the number of arcs in G- . This may have advantages when G- is much larger than G. We use this to generalize to digraphs a simple On + m log n algorithm of McConnell and Spinrad for finding the modular decomposition of undirected graphs. A key step is finding the strongly-connected components of a digraph F in G-s equivalence class, where F may have ~m log n arcs.

Mots-clés : algorithmes de graphes modular decomposition data structures search strategies structures de données stratégies de recherche décomposition modulaire efficient graph algorithms

Autor: Elias Dahlhaus - Jens Gustedt - Ross M. Mcconnell -



Documentos relacionados