Skip to main content

2017 | OriginalPaper | Buchkapitel

4. Hypergraphs and Exact Transversals

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The notion of a hypergraph was first used in the second half of the previous century. In 1973, a French mathematician, Claude Berge, published a monograph, in which a knowledge of hypergraphs was formalized and uniformed. This chapter deals with the hypergraph theory. At the beginning, well-known notations are presented. The remaining two sections of this chapter introduce new definitions, properties, algorithms, and theorems regarding hypergraphs and c-exact hypergraphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Anderson M, Meyer B, Olivier P (2011) Diagrammatic representation and reasoning. Springer Science & Business Media Anderson M, Meyer B, Olivier P (2011) Diagrammatic representation and reasoning. Springer Science & Business Media
2.
Zurück zum Zitat Bailey J, Manoukian T, Ramamohanarao K (2003) A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In: ICDM, IEEE Computer Society, pp 485–488 Bailey J, Manoukian T, Ramamohanarao K (2003) A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In: ICDM, IEEE Computer Society, pp 485–488
3.
Zurück zum Zitat Berge C (1973) Graphs and hypergraphs. North-Holland Pub. Co., American Elsevier Pub. Co., Amsterdam, New YorkMATH Berge C (1973) Graphs and hypergraphs. North-Holland Pub. Co., American Elsevier Pub. Co., Amsterdam, New YorkMATH
4.
Zurück zum Zitat Berge C (1984) Hypergraphs: combinatorics of finite sets, vol 45. Elsevier Berge C (1984) Hypergraphs: combinatorics of finite sets, vol 45. Elsevier
5.
Zurück zum Zitat Berge C (1989) Hypergraphs: combinatorics of finite sets, North-Holland Berge C (1989) Hypergraphs: combinatorics of finite sets, North-Holland
6.
Zurück zum Zitat Boros E, Gurvich V, Khachiyan L, Makino K (2000) An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process Lett 10:253–266MathSciNetCrossRef Boros E, Gurvich V, Khachiyan L, Makino K (2000) An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process Lett 10:253–266MathSciNetCrossRef
7.
Zurück zum Zitat Bothorel C, Bouklit M (2011) An algorithm for detecting communities in folksonomy hypergraphs. In: I2CS 2011: 11th international conference on innovative internet community services, LNI, pp 159–168 Bothorel C, Bouklit M (2011) An algorithm for detecting communities in folksonomy hypergraphs. In: I2CS 2011: 11th international conference on innovative internet community services, LNI, pp 159–168
8.
Zurück zum Zitat Dekker L, Smit W, Zuidervaart J (2013) In: Massively parallel processing applications and development: proceedings of the 1994 EUROSIM conference on massively parallel processing applications and development, Delft, The Netherlands, 21–23 June 1994, Elsevier Dekker L, Smit W, Zuidervaart J (2013) In: Massively parallel processing applications and development: proceedings of the 1994 EUROSIM conference on massively parallel processing applications and development, Delft, The Netherlands, 21–23 June 1994, Elsevier
9.
10.
Zurück zum Zitat Eiter T, Gottlob G (1995) Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput 24(6):1278–1304MathSciNetCrossRefMATH Eiter T, Gottlob G (1995) Identifying the minimal transversals of a hypergraph and related problems. SIAM J Comput 24(6):1278–1304MathSciNetCrossRefMATH
11.
Zurück zum Zitat Eiter T, Gottlob G, Makino K (2002) New results on monotone dualization and generating hypergraph transversals. SIAM J Comput 14–22 Eiter T, Gottlob G, Makino K (2002) New results on monotone dualization and generating hypergraph transversals. SIAM J Comput 14–22
12.
Zurück zum Zitat Hodkinson I, Otto M (2003) Finite conformal hypergraph covers and gaifman cliques in finite structures. Bull Symb Logic 9:387–405MathSciNetCrossRefMATH Hodkinson I, Otto M (2003) Finite conformal hypergraph covers and gaifman cliques in finite structures. Bull Symb Logic 9:387–405MathSciNetCrossRefMATH
13.
Zurück zum Zitat Kavvadias D, Stavropoulos EC (1999) Evaluation of an algorithm for the transversal hypergraph problem. In Proceedings of the 3rd international workshop on algorithm engineering, Springer, London, UK, pp 72–84 Kavvadias D, Stavropoulos EC (1999) Evaluation of an algorithm for the transversal hypergraph problem. In Proceedings of the 3rd international workshop on algorithm engineering, Springer, London, UK, pp 72–84
14.
Zurück zum Zitat Knuth D (2000) Dancing links. In: Millennial perspectives in computer science, Palgrave, pp 187–214 Knuth D (2000) Dancing links. In: Millennial perspectives in computer science, Palgrave, pp 187–214
15.
Zurück zum Zitat Lovász L (1972) Normal hypergraphs and the weak perfect graph conjecture. Discret Math 2:253–267CrossRefMATH Lovász L (1972) Normal hypergraphs and the weak perfect graph conjecture. Discret Math 2:253–267CrossRefMATH
16.
Zurück zum Zitat Mishra N, Pitt L (1997) Generating all maximal independent sets of bounded-degree hypergraphs. In: COLT ’97: Proceedings of the 10th annual conference on Computational learning theory, ACM, New York, NY, USA, pp 211–217 Mishra N, Pitt L (1997) Generating all maximal independent sets of bounded-degree hypergraphs. In: COLT ’97: Proceedings of the 10th annual conference on Computational learning theory, ACM, New York, NY, USA, pp 211–217
17.
Zurück zum Zitat Rauf I (2011) Polynomially solvable cases of hypergraph transversal and related problems. Doctoral dissertation, Universität des Saarlandes, Saarbrücken, Oct 2011 Rauf I (2011) Polynomially solvable cases of hypergraph transversal and related problems. Doctoral dissertation, Universität des Saarlandes, Saarbrücken, Oct 2011
18.
Zurück zum Zitat Wiśniewska M (2012) Application of hypergraphs in decomposition of discrete systems, vol 23. Lecture Notes in Control and Computer Science University of Zielona Góra Press, Zielona Góra Wiśniewska M (2012) Application of hypergraphs in decomposition of discrete systems, vol 23. Lecture Notes in Control and Computer Science University of Zielona Góra Press, Zielona Góra
19.
Zurück zum Zitat Wiśniewska M, Adamski M, Wiśniewski R (2011) Exact transversals in decomposition of Petri nets into concurrent subnets. Meas Autom Monit 58(8):851–853 in Polish Wiśniewska M, Adamski M, Wiśniewski R (2011) Exact transversals in decomposition of Petri nets into concurrent subnets. Meas Autom Monit 58(8):851–853 in Polish
Metadaten
Titel
Hypergraphs and Exact Transversals
verfasst von
Remigiusz Wiśniewski
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-45811-3_4