Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs | SpringerLink
Skip to main content
Springer Nature Link
Log in

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2005)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3787))

Included in the following conference series:

Abstract

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: a Survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (1999)

    Google Scholar 

  2. Corneil, D.G., Perl, Y., Stewart, L.K.: A linear time recognition algorithm for cographs. SIAM Journal on Computing 14(4), 926–934 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  3. Crespelle, C., Paul, C.: Fully-dynamic recognition algorithm and certificate for directed cographs. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 93–104. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  4. de Montgolfier, F.: Décomposition modulaire des graphes - Théorie, extensions et algorithmes. PhD thesis, Université de Montpellier 2, France (2003)

    Google Scholar 

  5. Gallai, T.: Transitiv orientierbare graphen. Acta Math. Acad. Sci. Hungar. 18, 25–66 (1967)

    Article  MATH  MathSciNet  Google Scholar 

  6. Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)

    MATH  Google Scholar 

  7. Hell, P., Shamir, R., Sharan, R.: A fully dynamic algorithm for recognizing and representing proper interval graphs. SIAM Journal on Computing 31(1), 289–305 (2002)

    Article  MathSciNet  Google Scholar 

  8. Ibarra, L.: Fully dynamic algorithms for chordal graphs. In: 10th ACM-SIAM Annual Symposium on Discrete Algorithm (SODA 2003), pp. 923–924 (1999)

    Google Scholar 

  9. Muller, J.H., Spinrad, J.P.: Incremental modular decomposition algorithm. Journal of the Association for Computing Machinery 36(1), 1–19 (1989)

    MATH  MathSciNet  Google Scholar 

  10. Shamir, R., Sharan, R.: A fully dynamic algorithm for modular decomposition and recognition of cographs. Discrete Applied Mathematics 136(2-3), 329–340 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  11. Uno, T., Yagiura, M.: Fast algorithms to enumerate all common intervals of two permutations. Algorithmica 26(2), 290–309 (2000)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CNRS – Département Informatique, LIRMM, Montpellier

    Christophe Crespelle & Christophe Paul

Authors
  1. Christophe Crespelle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Christophe Paul
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. LITA, Université Paul Verlaine-Metz, 57045, Metz Cedex 01, France

    Dieter Kratsch

Rights and permissions

Reprints and permissions

Copyright information

© 2005 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Crespelle, C., Paul, C. (2005). Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs. In: Kratsch, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2005. Lecture Notes in Computer Science, vol 3787. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11604686_4

Download citation

  • DOI: https://doi.org/10.1007/11604686_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31000-6

  • Online ISBN: 978-3-540-31468-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics