Abstract
A complementation operation on a vertex of a digraph changes all outgoing edges into nonedges, and outgoing nonedges into edges. A similar operation is defined for incoming edges. This defines an equivalence relation where two graphs 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 of G's equivalence class in O(size(G)) time. We use this fact to obtain a simple O(n+mlogn) algorithm for modular decomposition of undirected graphs.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms, Addison-Wesley (1974)
Cournier, A., Habib, M.: A new linear algorithm for modular decomposition, CAAP '94: 19th international colloquium, lecture notes in computer science, Sophie Tison, ed., Edinburgh, UK (1994) 68–82
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Algorithms, MIT Press (1990)
Dahlhaus, E., Gustedt, J., McConnell, R.M.: Efficient and practical modular decomposition, Proc. 8th annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans (1997) 26–35
Ehrenfeucht, A., Gabow, H.N., McConnell, R.M., Sullivan, S.J.: An O(n 2) divide-and-conquer algorithm for the prime tree decomposition of two-structures and modular decomposition of graphs, Journal of Algorithms 16 (1994) 283–294
Ehrenfeucht, A., Rozenberg, G.: Angular 2-structures, Theoretical Computer Science 92 (1992) 227–248
Ehrenfeucht, A., Rozenberg, G.: Dynamic labeled 2-structures, Math. Struct. in Comp. Science 4 (1994) 433–455
Ehrenfeucht, A., Rozenberg, G.: Theory of 2-structures, part 1: clans, basic sub-classes, and morphisms, Theoretical Computer Science 70 (1990) 277–303
Ehrenfeucht, A., Rozenberg, G.: Theory of 2-structures, part 2: representations through labeled tree families, Theoretical Computer Science 70 (1990) 305–342
Habib, M., Paul C., Viennot, L.: Lex-BFS, a partition refining technique, manuscript.
McConnell, R.M., Spinrad, J.P.: Linear-time modular decomposition and efficient transitive orientation of comparability graphs, Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, Arlington, Virginia (1994) 536–545
McConnell, R.M., Spinrad, J.P.: Linear-time transitive orientation, “Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms”, New Orleans (1997) 19–25
Moehring, R.H.: Algorithmic aspects of comparability graphs and interval graphs, in Graphs and Orders, I. Rival, ed., D. Reidel (1985) 41–101.
Rose, D., Tarjan, R.E., Leuker, G.S.: Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput. 5 (1976) 266–283
Rotem, D., Urrutia, J.: Circular permutation graphs, Networks 12 (1982) 429–437
Spinrad, J.P.: Vertex partitioning, Manuscript.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
McConnell, R. (1997). Complement-equivalence classes on graphs. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds) Structures in Logic and Computer Science. Lecture Notes in Computer Science, vol 1261. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63246-8_11
Download citation
DOI: https://doi.org/10.1007/3-540-63246-8_11
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63246-7
Online ISBN: 978-3-540-69242-3
eBook Packages: Springer Book Archive