Skip to main content
Top

2017 | OriginalPaper | Chapter

4. Hypergraphs and Exact Transversals

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

Literature
1.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference Berge C (1984) Hypergraphs: combinatorics of finite sets, vol 45. Elsevier Berge C (1984) Hypergraphs: combinatorics of finite sets, vol 45. Elsevier
5.
go back to reference Berge C (1989) Hypergraphs: combinatorics of finite sets, North-Holland Berge C (1989) Hypergraphs: combinatorics of finite sets, North-Holland
6.
go back to reference 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.
go back to reference 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.
go back to reference 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
10.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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.
go back to reference 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
Metadata
Title
Hypergraphs and Exact Transversals
Author
Remigiusz Wiśniewski
Copyright Year
2017
DOI
https://doi.org/10.1007/978-3-319-45811-3_4