Generalization of Two Hypergraphs. Algorithm of Calculation of the Greatest Sub-Hypergraph Common to Two Hypergraphs Annotated by Semantic Information | SpringerLink
Skip to main content
Springer Nature Link
Log in

Generalization of Two Hypergraphs. Algorithm of Calculation of the Greatest Sub-Hypergraph Common to Two Hypergraphs Annotated by Semantic Information

  • Conference paper
Graph Based Representations in Pattern Recognition

Part of the book series: Computing Supplement ((COMPUTING,volume 12))

  • 154 Accesses

Abstract

The problem of the search of the greatest sub-hypergraph common to two hypergraph is a combinational search problem. The algorithm of exploration of all solutions has an exponential complexity according to the size of the two hypergraphs. In this article, we present methods to minimize the necessary time for the calculation of these solutions. These methods constitute a general framework of the study of these problems and can be used in many areas such natural language, pattern recognition or organic chemistry.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Chakrabarti, P. P., Ghose, S., Acharya, A., C. de Sarkar, S.: Heuristic search in restricted memory. Art. Intell. 41, 197–221 (1989).

    Article  MathSciNet  MATH  Google Scholar 

  2. Demko, Ch.: Contribution à la Gestion du Contexte pour un Système de Compréhension Automatique de la Langue. Thèse de doctorat, Université de Technologie de Compiègne, Compiègne, France, December 1992.

    Google Scholar 

  3. Gondran, M., Minoux, M.: Graphs and algorithms. New York: Wiley, 1990.

    Google Scholar 

  4. Shapiro, L. G., Haralick, R. M.: Relational matching. Appl. Optics 26, 1845–1851 (1987).

    Article  Google Scholar 

  5. Sowa, J.: Conceptual structures information processing in mind and machines. Reading: Addison-Wesley, 1984.

    Google Scholar 

  6. Vosselman, G.: Relational matching. Lecture Notes in Computer Science, Vol. 628. Berlin, Heidelberg, New York, Tokyo: Springer, 1992.

    Book  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire d’Informatique et d’Imagerie Industrielles, Université de La Rochelle, Avenue Marillac, F-17042, La Rochelle Cedex 1, France

    Ch. Demko

Authors
  1. Ch. Demko
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Laboratoire Reconnaisance de Formes et Vision, INSA, Lyon, France

    Jean-Michel Jolion

  2. Pattern Recognition and Image Processing Group, Institute of Automation, University of Vienna, Austria

    Walter G. Kropatsch

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Wien

About this paper

Cite this paper

Demko, C. (1998). Generalization of Two Hypergraphs. Algorithm of Calculation of the Greatest Sub-Hypergraph Common to Two Hypergraphs Annotated by Semantic Information. In: Jolion, JM., Kropatsch, W.G. (eds) Graph Based Representations in Pattern Recognition. Computing Supplement, vol 12. Springer, Vienna. https://doi.org/10.1007/978-3-7091-6487-7_1

Download citation

  • DOI: https://doi.org/10.1007/978-3-7091-6487-7_1

  • Publisher Name: Springer, Vienna

  • Print ISBN: 978-3-211-83121-2

  • Online ISBN: 978-3-7091-6487-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation