Have a personal or library account? Click to login
On vertex independence number of uniform hypergraphs Cover

On vertex independence number of uniform hypergraphs

Acta Universitatis Sapientiae, Informatica
Volume 6 (2014): Issue 1 (June 2014)
By: Tariq A. Chishti,  Guofei Zhou,  Shariefuddin Pirzada and  Antal Iványi  
Open Access
|Jun 2014

References

  1. [1] V. Abraham, Independence in hypergraphs. J. Indian Math. Soc. (N.S.), 78, 1-4 (2011) 1-7. ⇒141
    Search in Google Scholar
  2. [2] B. D. Acharya, Interrelations among the notions of independence, domination and full sets in a hypergraph, Nat. Acad. Sci. Lett. 13, 11 (1990) 421-422. ⇒ 142
    Search in Google Scholar
  3. [3] G. Agnarsson, A. Egilsson, M. M. Halldórson, Vertex coloring acyclic digraphs and their corresponding hypergraphs, Discrete Appl. Math. 156, 10 (2008) 1918-1928. ⇒142
    Search in Google Scholar
  4. [4] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, in: Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci. 5555, Springer, Berlin, 2009, 12-23. ⇒133, 138, 14110.1007/978-3-642-02927-1_3
    Search in Google Scholar
  5. [5] G. Agnarsson, M. M. Halldórson, E. Losievskaja, SDP-based algorithms for maximum independent set problems on hypergraphs, Theoret. Comp. Sci. 470 (2013) 1-9. ⇒133, 138, 14110.1016/j.tcs.2012.11.025
    Search in Google Scholar
  6. [6] M. Ajtai, P. Erdős, J. Komlós and E. Szemerédi, On Turán theorem for sparse graphs, Combinatorica 1, 3 (1981) 313-317. ⇒13410.1007/BF02579451
    Search in Google Scholar
  7. [7] M. Ajtai, P. Erdős, J. Komlós, E. Szemerédi, A dense infinite Sidon sequence, European J. Combin. 2, 1 (1981) 1-11. ⇒13410.1016/S0195-6698(81)80014-5
    Search in Google Scholar
  8. [8] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers, J. Combin. Theory Ser. A 29 (1980) 354-360. ⇒13410.1016/0097-3165(80)90030-8
    Search in Google Scholar
  9. [9] A. Alon, A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms 7, 4 (1986) 567-583. ⇒133, 13810.1016/0196-6774(86)90019-2
    Search in Google Scholar
  10. [10] N. Alon, P. Frankl, H. Huang, V. Rödl, A. Ruciński, Large matchings in uniform hypergraphs and the conjectures of Erdős and Samuels, J. Combin. Theory Ser. A 119, 6 (2012) 1200-1215. ⇒133, 138, 14210.1016/j.jcta.2012.02.004
    Search in Google Scholar
  11. [11] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 1992. ⇒134
    Search in Google Scholar
  12. [12] A. Alon, A. Uri, Y. Azar, Independent sets in hypergraphs with applications to routing via fixed paths. In: Randomization, approximation, and combinatorial optimization (Berkeley, CA, 1999), Lecture Notes in Comput. Sci. 1671, Springer, Berlin, 1999, 16-27. ⇒14110.1007/978-3-540-48413-4_3
    Search in Google Scholar
  13. [13] N. Alon, R. Yuster, On a hypergraph matching problem, Graphs Comb. 21 (2005) 377-384. ⇒14210.1007/s00373-005-0628-x
    Search in Google Scholar
  14. [14] E. Angel, R. Campigotto, C. Laforest, A new lower bound on the independence number of graphs, Discrete Appl. 161, 6 (2013) 847-852. ⇒13410.1016/j.dam.2012.10.001
    Search in Google Scholar
  15. [15] G. Ausiello, A. D’Atri, D. Sacc`a, Minimal representation of directed hypergraphs, SIAM J. Comput. 15 (1986) 418-431. ⇒13910.1137/0215029
    Search in Google Scholar
  16. [16] J. Bailey, T. Manoukian, K. Ramamohanaro, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, in: Proc. of the Third IEEE Int.l Conf. on Data Mining (ICDM03), 2003, 485-488. ⇒142
    Search in Google Scholar
  17. [17] J. Balogh, J. Butterfield, P. Hu, J. Lenz, D. Mubayi, On the chromatic thresholds of hypergraphs arXiv:1103.1416, 2013, 37 pages. ⇒142
    Search in Google Scholar
  18. [18] J. Balogh, R. Morris, W. Samotij, Independent sets in hypergraphs, arXiv:1204.6530, 2013, 42 pages. ⇒136
    Search in Google Scholar
  19. [19] Zs. Baranyai, On the factorization of the complete uniform hypergraph, in: A. Hajnal, R. Rado, V. T. Sós (Eds.), Infinite and Finite Sets, Proc. Coll. Keszthely, 1973, North-Holland, Amsterdam, Netherlands, 1975, pp. 91-108. ⇒142
    Search in Google Scholar
  20. [20] S. Behrens, C. Erbes, M. Ferrara, S. G. Hartke, B. Reiniger, H. Spinoza, C. Tomlinson, New results on degree sequences of uniform hypergraphs. Electron. J. Combin. 20, 4 (2013) #P14, 18 pages. ⇒139
    Search in Google Scholar
  21. [21] M. Behrisch, A. Coja-Oghlan, M. Kang, The asymptotic number of connected d-uniform hypergraphs, Combin. Probab. Comput. 23, 3 (2014) 367-385. ⇒13910.1017/S0963548314000029
    Search in Google Scholar
  22. [22] C. Berge, The Theory of Graphs and its Applications, Wiley, London, 1964. ⇒ 137
    Search in Google Scholar
  23. [23] E. Berger, R. Ziv, A note on the edge cover number and independence number in hypergraphs, Discrete Math. 308, 12 (2008) 2649-2654. ⇒14110.1016/j.disc.2007.05.006
    Search in Google Scholar
  24. [24] C. Bertram-Kretzberg, H. Lefmann, The algorithmic aspects of uncrowded hypergraphs. SIAM J. Comput. 29, 1 (1999) 201-230. ⇒14210.1137/S0097539797323716
    Search in Google Scholar
  25. [25] T. Biedl, E. D. Demaine, C. A. Duncan, R. Fleischer, S. G. Kobourov, Tight bounds on maximal and maximum matchings, Discrete Math. 285 (2004) 7-15. ⇒14110.1016/j.disc.2004.05.003
    Search in Google Scholar
  26. [26] V. Blinovsky, Fractional matching in hypergraphs, arXiv:1311.2671, 2013, 6 pages. ⇒141
    Search in Google Scholar
  27. [27] B. Bollobás, D. E. Daykin, P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. (2) 27, 1 (1976), 25-32. ⇒14110.1093/qmath/27.1.25
    Search in Google Scholar
  28. [28] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, arXiv:1308.2837, 2013, 16 pages. ⇒141
    Search in Google Scholar
  29. [29] A. Bonato, J. I. Brown, D. Mitsche, P. Pralat, Independence densities of hypergraphs, Europ. J. Combin. 40 (2014) 124-136. ⇒14110.1016/j.ejc.2014.03.001
    Search in Google Scholar
  30. [30] R. Boppana, M. M. Halldórson, Approximating maximum independent set by excluding subsets, BIT, 32 (1992) 160-196. ⇒133, 138
    Search in Google Scholar
  31. [31] M. Bordewich, M. Dyer, M. Karpiński, Path coupling using stopping times and counting independent sets and colorings in hypergraphs Random Structures Alg. 32, 3 (2008) 375-399. ⇒14110.1002/rsa.20204
    Search in Google Scholar
  32. [32] E. Boros, K. Elbassioni, V. Gurvich, L. Khachiyan,Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: LATIN 2004: Theoretical informatics, Lecture Notes in Comput. Sci. 2976, Springer, Berlin, 2004, 488-498. ⇒14110.1007/978-3-540-24698-5_52
    Search in Google Scholar
  33. [33] E. Boros, V. Gurvich, K. Elbassioni, L. Khachiyan, An efficient incremental algorithm for generating all maximal independent sets in hypergraphs of bounded dimension. Parallel Process. Lett. 10, 4 (2000) 253-266. ⇒14110.1142/S0129626400000251
    Search in Google Scholar
  34. [34] M. Borowiecki, D. Michalak, The independence graphs of hypergraphs and middle graphs, Discuss. Math. 7 (1985) 31-37. ⇒141
    Search in Google Scholar
  35. [35] Cs. Bujtás, Zs. Tuza, Uniform mixed hypergraphs: The possible numbers of colors, Graphs Combin., 24 (2008) 1-12. ⇒14210.1007/s00373-007-0765-5
    Search in Google Scholar
  36. [36] Y. Caro, New results on the independence number, Technical Report, 1979, Tel- Aviv University. ⇒134
    Search in Google Scholar
  37. [37] Y. Caro, A. Hansberg, New approach to the k-independence number of a graph. Electron. J. Combin. 20, 1 (2013) #P33, 17 pages. ⇒13510.37236/2646
    Search in Google Scholar
  38. [38] Y. Caro, Zs. Tuza, Improved lower bounds on k-independence, J. Graph Theory 15 (1991) 99-107. ⇒13510.1002/jgt.3190150110
    Search in Google Scholar
  39. [39] R. D. Carr, G. Lancia, S. Istrail, C. Genomics, Branch-and-Cut algorithms for independent set problems: Integrality gap and an application to protein structure alignment. SAND Report SAND2000-2171, Sandia National Laboratories, 2000. ⇒14210.2172/764804
    Search in Google Scholar
  40. [40] G. Chartrand, S. Schuster, On the independence number of complementary graphs, Trans. New York Acad. Sci., Series II 36, 3 (1974) 247-251. ⇒13910.1111/j.2164-0947.1974.tb01571.x
    Search in Google Scholar
  41. [41] M. Chellali, O. Favaron, A. Hansberg, L. Volkmann, k-domination and kindependence in graphs: a survey, Graphs Combin. 28, 1 (2012) 1-55. ⇒135, 13710.1007/s00373-011-1040-3
    Search in Google Scholar
  42. [42] M. Chellali, N. J. Rad, On k-independence critical graphs. Australas. J. Combin. 53 (2012) 289-298. ⇒135
    Search in Google Scholar
  43. [43] E. J. Cockayne, S. T. Hedetniemi, R. Laskar, Gallai theorems for graphs, hypergraphs and set systems, Discrete Math. 72 (1988) 35-47. ⇒14210.1016/S0167-5060(08)70769-6
    Search in Google Scholar
  44. [44] B. Csaba, T. A. Pick, A Shokoufandeh, A note on the Caro-Tuza bound on the independence number of uniform hypergraphs, Australas. J. Combin. 52 (2012) 235-242. ⇒135
    Search in Google Scholar
  45. [45] J. Cutler, A. J. Radcliffe, Hypergraph independent sets, Combin. Probab. Comput. 22, 1 (2013) 9-20. ⇒14110.1017/S0963548312000454
    Search in Google Scholar
  46. [46] B. C. Dean, S. M. Hedetniemi, S. T. Hedetniemii, J. Lewis, A. McRae, Matchability and k-maximal matchings. Discrete Math. 159, 1 (2011) 15-22. ⇒14110.1016/j.dam.2010.09.006
    Search in Google Scholar
  47. [47] A. Dudek, A. Frieze, A. Ruciński, M. ˇSileikis, Approximate counting of regular hypergraphs, Inf. Processing Letters, 113, 1921 (2013) 785-788. ⇒139, 14110.1016/j.ipl.2013.07.018
    Search in Google Scholar
  48. [48] K. Dutta, D. Mubayi, C. R. Subramanian, New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math. 26, 3 (2012) 1134-1147. ⇒13810.1137/110839023
    Search in Google Scholar
  49. [49] J. Edmonds, Paths, trees, and flowers, Canadian J. Math. 17 (1965) 449-467. ⇒133, 138, 14110.4153/CJM-1965-045-4
    Search in Google Scholar
  50. [50] J. Edmonds, Maximal matching and a polyhedron with 0, 1-vertices, J. Research Nat. Bureau Standards B-69 (1965) 125-130. ⇒133, 138, 14110.6028/jres.069B.013
    Search in Google Scholar
  51. [51] A. Eustis, Hypergraph Independence Numbers, PhD Thesis. University of California, San Diego. 2013. 123 pages. ⇒138
    Search in Google Scholar
  52. [52] A. Eustis, J. Verstra¨ete, On the independence number of Steiner systems, Combinatorics, Prob. Comp. 22, 2 (2013) 241-252. ⇒13810.1017/S0963548312000557
    Search in Google Scholar
  53. [53] S. Fajtlowicz, Independence, clique size and maximum degree, Combinatorica 4 (1984), 35-38. ⇒13610.1007/BF02579154
    Search in Google Scholar
  54. [54] O. Favoron, A. Hansberg, L. Volkmann, On k-domination and minimum degree in graphs, J. Graph Theory 57, 1 (2008) 33-40. ⇒135, 13710.1002/jgt.20279
    Search in Google Scholar
  55. [55] A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Appl. Math 131, 2 (2003) 385-400. ⇒140, 14210.1016/S0166-218X(02)00462-6
    Search in Google Scholar
  56. [56] P. Frankl, Improved bounds for Erdős matching conjecture, J. Combin. Theory Ser. A 120, 5 (2013) 1068-1072. ⇒14110.1016/j.jcta.2013.01.008
    Search in Google Scholar
  57. [57] P. Frankl, T. Luczak, K.Mieczkowska, On matchings in hypergraphs. Electron. J. Combin. 19, 2 (2012), #P42, 5 pages. ⇒14110.37236/2176
    Search in Google Scholar
  58. [58] P. Frankl, V. Rödl, Some Ramsey-Turn type results for hypergraphs. Combinatorica 8, 4 (1988) 323-332. ⇒14210.1007/BF02189089
    Search in Google Scholar
  59. [59] P. Frankl, V. Rödl, The uniformity lemma for hypergraphs, Graphs Combin. 8 (1992) 309-312. ⇒14210.1007/BF02351586
    Search in Google Scholar
  60. [60] M. Frieze, On the independence number of random graphs, Discrete Math. 81, 2 (1990) 171-175. ⇒13610.1016/0012-365X(90)90149-C
    Search in Google Scholar
  61. [61] Z. FÜredi, Matchings and covers in hypergraphs, Graphs Combin. 4 (1988) 115-206. ⇒14110.1007/BF01864160
    Search in Google Scholar
  62. [62] Z. Füredi, The number of maximal independent sets in connected graphs, J. Graph Theory, 11, 4 (1995) 463-470. ⇒13710.1002/jgt.3190110403
    Search in Google Scholar
  63. [63] Z. FÜredi, Linear trees in uniform hypergraphs, Europ. J. Combin. 35 (2014) 264-272. ⇒14210.1016/j.ejc.2013.06.022
    Search in Google Scholar
  64. [64] Z. Füredi, M. Ruszinkó, Uniform hypergraphs containing no grids, Adv. Math. 240 (2013) 302-324. ⇒14210.1016/j.aim.2013.03.009
    Search in Google Scholar
  65. [65] H. M. Gabow, An efficient implementation of Edmonds’ algorithm for maximum matching on graphs, J. ACM 23, 2 (1976) 221-234. ⇒14110.1145/321941.321942
    Search in Google Scholar
  66. [66] H. M. Gabow, Data structures for weighted matchings and nearest nearest common ancestors with linking, in: Proc. 1st Annual ACM-SIAM Symp. Discrete Algorithms 1990, 434-443. ⇒141
    Search in Google Scholar
  67. [67] T. Gallai, Über extreme Punkt- und Kantenmengen, Ann. Univ. Sci. Budapest. de Rolando Eötvös Nominatae, Sect. Math. 2 (1959) 133-138. ⇒139
    Search in Google Scholar
  68. [68] G. Gallo, G. Longo, S. Nguyen, S. Pallottino, Directed hypergraphs and applications, Discrete Appl. Math 42, 2-3 (1993) 177-201. ⇒140, 14210.1016/0166-218X(93)90045-P
    Search in Google Scholar
  69. [69] S.. Gaspers, D. Kratsch, M. Liedloff, Independent sets and bicliques in graphs, in: H. Broersma, T. Erlebach, T. Friedetzky, D. Paulusma (eds.) Graph-Theoretic Concepts in Computer Science (Int. Workshop WG2008, Durham, UK, June 30, 2008-July 2, 2008), Lecture Notes in Comput. Sci. 5344, Springer, 2008, 171-182. ⇒13610.1007/978-3-540-92248-3_16
    Search in Google Scholar
  70. [70] C. Greenhill, The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complexity 9, 1 (2000) 52-72. ⇒14110.1007/PL00001601
    Search in Google Scholar
  71. [71] C. Greenhill, A. Rucinski, N. C. Wormald, Random hypergraph processes with degree restrictions, Graphs Combin. 20 (2004) 319-332. ⇒14110.1007/s00373-004-0571-2
    Search in Google Scholar
  72. [72] J. Griggs, Lower bounds on the independence number in terms of the degrees, J. Comb. Theory, Ser. B 34 (1983) 22-39. ⇒134, 14510.1016/0095-8956(83)90003-5
    Search in Google Scholar
  73. [73] J. L. Gross, J. Yellen, P. Zhang, Handbook of Graph Theory, CRC Press, Boca Raton, FL, 2014. ⇒133, 13810.1201/b16132
    Search in Google Scholar
  74. [74] D. Gunopolus, R. Khardon, H. Mannila, H. Toivonen, Data mining, hypergraph traversals, and machine learning. Proc. PODS’97, 1997, pp. 209-2016. ⇒14210.1145/263661.263684
    Search in Google Scholar
  75. [75] M. M. Halldórson, Approximations of weighted independent set and hereditary subset problems, J. Graph Algorithms Appl. 4, 1 (2000) 1-16. ⇒13610.7155/jgaa.00020
    Search in Google Scholar
  76. [76] M. M. Halldórson, E. Losievskaja, Independent sets in bounded-degree hypergraphs, Discrete Appl. Math 157, 8 (2009) 1773-1786. ⇒14110.1016/j.dam.2008.11.013
    Search in Google Scholar
  77. [77] J. Han, Near perfect matchings in k-uniform hypergraphs, arXiv:1404.1136, 2014, 7 pages. ⇒141
    Search in Google Scholar
  78. [78] H. Hàn, Y. Person, M. Schaht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math. 23, 2 (2009) 732-748. ⇒141, 14210.1137/080729657
    Search in Google Scholar
  79. [79] A. Hansberg, R. Pepper, On k-domination and j-independence in graphs. Discrete Appl. Math 161, 10-11 (2013) 1472-1480. ⇒135, 136, 13710.1016/j.dam.2013.02.008
    Search in Google Scholar
  80. [80] J. Harant, A lower bound on independence number of a graph, Discrete Math. 188, 13 (1998) 239243. ⇒13410.1016/S0012-365X(98)00048-X
    Search in Google Scholar
  81. [81] J. Harant, A lower bound on independence in terms of degrees, Discrete Appl. Mathematics 159, 10 (2011) 966-970. ⇒134, 13510.1016/j.dam.2011.03.003
    Search in Google Scholar
  82. [82] J. Harant, A. Pruchnewski, M. Voigt, On dominating sets and independent sets of graphs, Combinatorics, Prob. Comp. 8, 6 (1999) 547-553. ⇒13710.1017/S0963548399004034
    Search in Google Scholar
  83. [83] J. Harant, D. Rautenbach, Independence in connected graphs. Discrete Appl. Math 159, 1 (2011) 79-86. ⇒13510.1016/j.dam.2010.08.029
    Search in Google Scholar
  84. [84] J. Harant, I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math., 232, 1-3 (2001) 131-138. ⇒13510.1016/S0012-365X(00)00298-3
    Search in Google Scholar
  85. [85] J. Harant, I. Schiermeyer, A lower bound on the independence number of a graph in terms of degrees. Discuss. Math. Graph Theory 26, 3 (2006), 431-437. ⇒13510.7151/dmgt.1335
    Search in Google Scholar
  86. [86] M. A. Henning, C. Löwenstein, D. Rautenbach, Independent sets and matchings in subcubic graphs. Discrete Math., 312, 11 (2012) 1900-1910. ⇒14110.1016/j.disc.2012.03.002
    Search in Google Scholar
  87. [87] M. A. Henning, C. Löwenstein, J. Southey, A. Yeo. A new lower bound on the independence number of a graph and applications, Electron. J. Comb. 21, 1 (2014) #P1.38. ⇒13610.37236/3601
    Search in Google Scholar
  88. [88] M. A. Henning, A. Yeo, Tight lower bounds on the size of a maximum matching in a regular graph. Graphs Combin. 3, 6 (2007) 647-657. ⇒14110.1007/s00373-007-0757-5
    Search in Google Scholar
  89. [89] M. A. Henning, A. Yeo, Lower bounds on the size of maximum independent sets and matchings in hypergraphs of rank three. J. Graph Theory, 72, 1-2 (2013) 220-245. ⇒135, 141, 14210.1002/jgt.21640
    Search in Google Scholar
  90. [90] T. Hofmeister, H. Lefmann, Approximating maximum independent sets in uniform hypergraphs. In: Mathematical Foundations of Computer Science, 1998, Brno, Lecture Notes in Comput. Sci. 1450, Springer, Berlin, 1998, 562-570. ⇒ 14110.1007/BFb0055806
    Search in Google Scholar
  91. [91] J. E. Hopcroft, R. M. Karp, An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput., 2 (1973) 225-231. ⇒14110.1137/0202019
    Search in Google Scholar
  92. [92] H. Huang, P.-S. Loh, B. Sudakov, The size of a hypergraph and its matching number, Combin. Probab. Comput. 21, 3 (2012) 442-450. ⇒141, 14210.1017/S096354831100068X
    Search in Google Scholar
  93. [93] D. S. Johnson, M. Yannakakis, On generating all maximal independent sets, Inf. Processing Letters 27, 3 (1988) 119-123. ⇒133, 138, 141, 14210.1016/0020-0190(88)90065-8
    Search in Google Scholar
  94. [94] T. Johnston, L. Lu, Turn problems on non-uniform hypergraphs, arXiv:1301.1870, 2013. ⇒14210.37236/3901
    Search in Google Scholar
  95. [95] T. Johnston, L. Lu, Strong jumps and Lagrangians of non-uniform hypergraphs, arXiv:1403.1220, 2014. ⇒14210.37236/3901
    Search in Google Scholar
  96. [96] B. K. Jose, Zs. Tuza, Hypergraph domination and strong independence. Appl. Anal. Discrete Math. 3, 2 (2009) 347-358. ⇒14210.2298/AADM0902347J
    Search in Google Scholar
  97. [97] E. Jucovič, F. Olejník, On chromatic and achromatic numbers of uniform hypergraphs, Časopis Pĕstováni Matematiky, 99 (1974) 123-130. ⇒139, 14210.21136/CPM.1974.117834
    Search in Google Scholar
  98. [98] A. Kako, T. Ono, T. Hirata, M. M. Halldórson, Approximation algorithms for the weighted independent set problem in sparse graphs, Discrete Appl. Math 157, 4 (2009) 617-626. ⇒13610.1016/j.dam.2008.08.027
    Search in Google Scholar
  99. [99] M. Karonski, T. Luczak, The number of connected sparsely edged uniform hypergraphs, Discrete Math. 171, 1-3 (1997) 153-167. ⇒14210.1016/S0012-365X(96)00076-3
    Search in Google Scholar
  100. [100] R.M. Karp, U.V. Vazirani, V.V. Vazirani, An optimal online algorithm for optimal bipartite matching, in: Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing (STOC ’90), ACM, New York, NY, 1990, 352-358. ⇒14110.1145/100216.100262
    Search in Google Scholar
  101. [101] R. M. Karp, A. Widgerson, A fast parallel algorithm for the maximal independent set problem, J. ACM 32, 4 (1985) 762-773. ⇒133, 13810.1145/4221.4226
    Search in Google Scholar
  102. [102] G. O. H. Katona, Continuous versions of some extremal hypergraph problems, in: Combinatorics (Keszthely, Hungary, 1976), Coll. Math. Soc. J. Bolyai 18 (Math. Soc. J. Bolyai, Budapest, 1978), 653-678. ⇒142
    Search in Google Scholar
  103. [103] G. O. H. Katona, Continuous versions of some extremal hypergraph problems II, Acta Math. Acad. Sci. Hungar. 35 (1980) 67-77. ⇒14210.1007/BF01896826
    Search in Google Scholar
  104. [104] P. Keevash, F. Knox, R. Mycroft, Polynomial-time perfect matchings in dense hypergraphs, arXiv:1307.2608, 2013. 62 pages. ⇒14110.1145/2488608.2488647
    Search in Google Scholar
  105. [105] P. Keevash, R. Mycroft, A geometric theory for hypergraph matching, arXiv:1108.1757, 2013, 101 pages. ⇒14110.1007/978-88-7642-475-5_23
    Search in Google Scholar
  106. [106] P. Keevash, B. Sudakov, On a hypergraph Turán problem of Frankl, Combinatorica 25, 6 (2005) 673-706. ⇒14210.1007/s00493-005-0042-2
    Search in Google Scholar
  107. [107] P. Kelsen, On the parallel complexity of computing a maximal independent set in a hypergraph. In: Proc. Twenty-fourth Annual ACM Symp. Theory Comp. (STOC’92), ACM New York, NY, 1992, 339-350. ⇒138, 14210.1145/129712.129745
    Search in Google Scholar
  108. [108] L. Khachiyan, E. Boros, V. Gurvich, K. Elbassioni, Computing many maximal independent sets for hypergraphs in parallel, Parallel Process. Lett. 17, 2 (2007) 141-152. ⇒14110.1142/S0129626407002934
    Search in Google Scholar
  109. [109] I. Khan, Perfect matchings in 3-uniform hypergraphs with large vertex degree. SIAM J. Discrete Math. 27, 2 (2013) 1021-1039. ⇒14110.1137/10080796X
    Search in Google Scholar
  110. [110] M. A. Khan, S. , K. K. Kayibi, Scores, inequalities and regular hypertournaments, Math. Inequal. Appl. 15, 2 (2012), 343-351. ⇒13910.7153/mia-15-28
    Search in Google Scholar
  111. [111] Y. Kohayakawa, V. Rödl, J. Skokan, Hypergraphs, quasi-randomness, and conditions for regularity, J. Combin. Theory Ser. A 97, 2 (2002) 307-352. ⇒14210.1006/jcta.2001.3217
    Search in Google Scholar
  112. [112] V. Kolmogorov, V. Blossom, A new implementation of a minimum cost perfect matching algorithm, Math. Programming Pomp. 1 (2009) 43-67. ⇒14110.1007/s12532-009-0002-8
    Search in Google Scholar
  113. [113] D. Kőnig, Graphs and matrices (Hungarian), Matematikai és Fizikai Lapok 38 (1931) 116-119. ⇒141
    Search in Google Scholar
  114. [114] A. Kostochka, D. Mubayi, J. Verstra¨ete, On independent sets in hypergraphs, Random Structures Algorithms 44, 2 (2014) 224-239. ⇒14210.1002/rsa.20453
    Search in Google Scholar
  115. [115] M. Krivelevich, Approximate set covering in uniform hypergraphs, J. Algorithms 25, 1 (1997) 118-143. ⇒14210.1006/jagm.1997.0872
    Search in Google Scholar
  116. [116] M. Krivelevich, R. Nathaniel, B. Sudakov, Approximating coloring and maximum independent sets in 3-uniform hypergraphs, J. Algorithms 41, 1 (2001) 99-113. ⇒14210.1006/jagm.2001.1173
    Search in Google Scholar
  117. [117] D. KÜhn, D. Loose, Hamilton cycles in 3-uniform hypergraphs of high minimum degree, J. Comb. Theory, Ser. B 96, 6 (2006) 767-821. ⇒14210.1016/j.jctb.2006.02.004
    Search in Google Scholar
  118. [118] D. KÜhn, D. Osthus, A. Treglown, Matchings in 3-uniform hypergraphs, J. Combinatorial Theory Series B 103 (2013) 291-305. ⇒14110.1016/j.jctb.2012.11.005
    Search in Google Scholar
  119. [119] D. KÜhn, D. Osthus, T. Townsend, Fractional and integer matchings in uniform hypergraphs, Europ. J. Combin. 38 (2014) 83-96. ⇒14110.1016/j.ejc.2013.11.006
    Search in Google Scholar
  120. [120] R. Laskar, B. Auerbach, On complementary graphs with no isolated vertices, Discrete Math. 24, 2 (1978) 113-118. ⇒14010.1016/0012-365X(78)90189-9
    Search in Google Scholar
  121. [121] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, Generating all maximal independent sets: NP-hardness and polynomial-time algorithms, SIAM J. Comput. 9, 3 (1980), 558-565. ⇒133, 13810.1137/0209042
    Search in Google Scholar
  122. [122] V. V. Lepin, An algorithm for finding the independence number of a recursively generated hypergraph (Russian), Dokl. Nats. Akad. Nauk Belarusi 49, 2 (2005), 22-25, 125. ⇒141
    Search in Google Scholar
  123. [123] Y. Li, C. Rousseau, On book-complete graph Ramsey numbers, J. Comb. Theory, Ser. B 68, 1 (1996) 36-44. ⇒14210.1006/jctb.1996.0055
    Search in Google Scholar
  124. [124] Y. Li, C. Rousseau, W. Zang, Asymptotic upper bound for Ramsey functions, Graphs Combin., 17 (2001) 123-128. ⇒14210.1007/s003730170060
    Search in Google Scholar
  125. [125] Y. Li, W. Zang, Differential methods for finding independent sets in hypergraphs, SIAM J. Discrete Math. 20 (2006) 96-104. ⇒141, 14210.1137/S0895480104442571
    Search in Google Scholar
  126. [126] E. Losievskaja, Approximation Algorithms for Independent Set Problems on Hypergraphs, PhD Dissertation, School of Computer Science Reykjavik University, Reykyavik, 2009, XV + 80 pages. ⇒133, 138, 141
    Search in Google Scholar
  127. [127] L. Lovász, M. D. Plummer, Matching Theory, North Holland, Amsterdam, 1986. ⇒141
    Search in Google Scholar
  128. [128] M. Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J. Comput. 15, 1 (1976) 1036-1053. ⇒133, 13810.1137/0215074
    Search in Google Scholar
  129. [129] T. Luczak, E. Szymańska, A parallel randomized algorithm for finding a maximal independent set in a linear hypergraph, J. Algorithms 25, 2 (1997) 311-320. ⇒14210.1006/jagm.1997.0884
    Search in Google Scholar
  130. [130] D. Maier, Minimum covers in the relational data base model, J. Assoc. Comp. Mach. 27 (1980) 664-674. ⇒14210.1145/322217.322223
    Search in Google Scholar
  131. [131] K. Markström, A. Ruciński, Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees, Europ. J. Combin. 32, 5 (2011) 677-687. ⇒14110.1016/j.ejc.2011.02.001
    Search in Google Scholar
  132. [132] S. Micali, V.V. Vazirani, An O( √ VE) algorithm for finding maximum matching in general graphs, Proc. 21st Annual IEEE Symposium on Foundations of Computer Science (1980) 17-27. ⇒14110.1109/SFCS.1980.12
    Search in Google Scholar
  133. [133] K. Mulmuley, U.V. Vazirani, V.V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7, 1 (1987) 105-114. ⇒14110.1007/BF02579206
    Search in Google Scholar
  134. [134] V. Nikiforov, An analytic theory of extremal hypergraph problems, arXiv:1305.1073, 2013, 31 pages. ⇒142
    Search in Google Scholar
  135. [135] F. Olejník, On total matching numbers and total covering numbers for k-uniform hypergraphs. Math. Slovaca 34, 3 (1984), 319-328. ⇒141
    Search in Google Scholar
  136. [136] F. Olejník, On edge independence numbers and edge covering numbers of kuniform hypergraph, Math. Slovaca 39, 1 (1989) 21-26. ⇒138, 139, 140
    Search in Google Scholar
  137. [137] L. özkahiya, M. E. Young, Anti-Ramsey number of matchings in hypergraphs, Discrete Math., 313, 20 (2013), 2359-2364. ⇒14110.1016/j.disc.2013.06.015
    Search in Google Scholar
  138. [138] S. Pirzada, Hypertournaments-scores, losing scores, total scores and degrees. J. Combin. Math. Combin. Comput. 84 (2013) 99-112. ⇒139
    Search in Google Scholar
  139. [139] S. Pirzada, G. Zhou, On k-hypertournament losing scores, Acta Univ. Sapientiae, Informatica 2, 1 (2010) 5-9. ⇒139
    Search in Google Scholar
  140. [140] S. Pirzada, G. Zhou, A. Iványi, Score lists in multipartite hypertournaments, Acta Univ. Sapientiae, Informatica 2, 2 (2010) 184-193. ⇒139
    Search in Google Scholar
  141. [141] K. Plociennik, Approximating independent set and coloring in random uniform hypergraphs. In: Mathematical Foundations of Computer Science (2008), Lecture Notes in Comput. Sci. 5162, Springer, Berlin, 2008, 539-550. ⇒14110.1007/978-3-540-85238-4_44
    Search in Google Scholar
  142. [142] M. D. Plummer, Matching theory-a sampler: from Dénes König to the present, Discrete Math. 100 (1992) 172-219. ⇒14110.1016/0012-365X(92)90640-2
    Search in Google Scholar
  143. [143] A. Pruchnewski, On the domination number of graphs, Discrete Math., 251, 1-3 (2002) 129-136. ⇒13710.1016/S0012-365X(01)00334-X
    Search in Google Scholar
  144. [144] J. Qian, Enumeration of unlabeled uniform hypergraphs, Electronic J. Combin 20, 1 (2013), P46, 10 pages ⇒13910.37236/2766
    Search in Google Scholar
  145. [145] J. Qian, Enumeration of unlabeled uniform hypergraphs. Discrete Math. 326 (2014), 66-74. ⇒13910.1016/j.disc.2014.03.005
    Search in Google Scholar
  146. [146] V. Rödl, A. Ruci´ski, M. Schacht, E. Szemerédi, A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Comment. Math. Univ. Carolin. 49, 4 (2008) 633-636. ⇒141
    Search in Google Scholar
  147. [147] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in uniform hypergraphs with large minimum degree, Europ. J. Combin. 27 (2006) 1333-1349. ⇒14110.1016/j.ejc.2006.05.008
    Search in Google Scholar
  148. [148] V. Rödl, A. Ruciński, E. Szemerédi, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory Ser. A 116, 3 (2009), 613-636. ⇒14110.1016/j.jcta.2008.10.002
    Search in Google Scholar
  149. [149] S. Sakai, M. Mitsunori, K. Yamazaki, A note on greedy algorithms for the maximum weighted independent set problem. Discrete Appl. Math 126, 2-3 (2003) 313-322. ⇒13610.1016/S0166-218X(02)00205-6
    Search in Google Scholar
  150. [150] S. M. Selkow, A probabilistic lower bound on the independence number of graphs. Discrete Math. 132 (1994) 363-365. ⇒134, 13510.1016/0012-365X(93)00102-B
    Search in Google Scholar
  151. [151] H. Shachnai, A. Srinivasan, Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18, 3 (2004/05) 488-500. ⇒14110.1137/S0895480102419731
    Search in Google Scholar
  152. [152] J. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983) 83-87. ⇒134, 136, 141, 14510.1016/0012-365X(83)90273-X
    Search in Google Scholar
  153. [153] J. Spencer, Turán’s theorem for k-graphs, Discrete Math. 2 (1972) 183-186. ⇒ 13610.1016/0012-365X(72)90084-2
    Search in Google Scholar
  154. [154] E. Szymańska, The complexity of 2-coloring and strong coloring in uniform hypergraphs of high minimum degre, Discrete Math. Theor. Comput. Sci. 15, 3 (2013) 121-137. ⇒141, 14210.46298/dmtcs.596
    Search in Google Scholar
  155. [155] R. E. Tarjan, A. E. Trojanowski, Finding a maximum independent set, SIAM J. Comput. 6, 3 (1977) 537-546. ⇒133, 138, 14110.1137/0206038
    Search in Google Scholar
  156. [156] T. Thiele, A lower bound on the independence number of arbitrary hypergraphs, J. Graph Theory 30, 3 (1999) 213-221. ⇒13510.1002/(SICI)1097-0118(199903)30:3<;213::AID-JGT6>3.0.CO;2-Q
    Search in Google Scholar
  157. [157] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs, J. Combin. Theory Ser. A 119, 7 (2012) 1500-1522. ⇒141, 14210.1016/j.jcta.2012.04.006
    Search in Google Scholar
  158. [158] A. Treglown, Y. Zhao, Exact minimum degree thresholds for perfect matchings in uniform hypergraphs II., J. Combin. Theory Ser. A 120, 7 (2013) 1463-1482. ⇒141, 14210.1016/j.jcta.2013.04.008
    Search in Google Scholar
  159. [159] P. Turán, On the theory of graphs, Colloq. Math. 3 (1954) 19-30. ⇒133, 13410.4064/cm-3-1-19-30
    Search in Google Scholar
  160. [160] Zs. Tuza, Extensions of Gallai’s graph covering theorems for uniform hypergraphs, J. Combin. Theory, Series B 52, 1 (1991) 92-96. ⇒139, 14210.1016/0095-8956(91)90094-Z
    Search in Google Scholar
  161. [161] V. V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O( √ VE) maximum matching algorithm, Combinatorica 14, 1 (1994) 71-109. ⇒13310.1007/BF01305952
    Search in Google Scholar
  162. [162] V. V. Vazirani, An improved definition of blossoms and a simpler proof of the MV matching algorithm, arXiv:1210.4594, 2013, 32 pages. ⇒133
    Search in Google Scholar
  163. [163] A. Vietri, The complexity of arc-colorings for directed hypergraphs, Discrete Appl. Math 143,1-3 (2004) 266-271. ⇒14010.1016/j.dam.2004.04.002
    Search in Google Scholar
  164. [164] C. Wang, G. Zhou, Note on the degree sequences of k-hypertournaments, Note on the degree sequences of k-hypertournaments, Discrete Math. 308, 11 (2008) 2292-2296. ⇒139
    Search in Google Scholar
  165. [165] V. Wei, A lower bound on the stability number of a simple graph, Bell Laboratories Technical Memorandum, 1981, No. 81-11217-9. ⇒134
    Search in Google Scholar
  166. [166] E. W. Weisstein, Independent Edge Set. Downloaded 9 May 2014. ⇒133
    Search in Google Scholar
  167. [167] Wikipedia, Independent Set. Downloaded 9 May 2014. ⇒133, 138
    Search in Google Scholar
  168. [168] R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs. Inf. Processing Letters 99, 4 (2006) 130-134. ⇒14110.1016/j.ipl.2006.04.005
    Search in Google Scholar
  169. [169] R. Yuster, Maximum matching in regular and almost regular graphs, Algorithmica 66, 1 (2013) 87-92. ⇒141, 14210.1007/s00453-012-9625-7
    Search in Google Scholar
  170. [170] G. Zhou, Y. Li, Independence numbers of hypergraphs with sparse neighborhoods, Europ. J. Combin. 25, 3 (2004) 355-362. ⇒134, 140, 141, 14210.1016/j.ejc.2003.09.008
    Search in Google Scholar
  171. [171] G. Zhou, S. Pirzada, Degree sequence of oriented k-hypergraphs, J. Appl. Math. Comput. 27, 1-2 (2008) 149158. ⇒13910.1007/s12190-008-0047-2
    Search in Google Scholar
  172. [172] G. Zhou, T. Yao, K. Zhang, On score sequences of k-hypertournaments, Europ. J. Combin. 21, 8 (2000) 993-1000. ⇒13910.1006/eujc.2000.0393
    Search in Google Scholar
DOI: https://doi.org/10.2478/ausi-2014-0022 | Journal eISSN: 2066-7760
Journal RSS Feed
Language: English
Page range: 132 - 158
Submitted on: Jan 15, 2014
|
Published on: Jun 27, 2014
Published by: Sapientia Hungarian University of Transylvania
In partnership with: Paradigm Publishing Services
Publication frequency: 2 issues per year
Keywords:
uniform hypergraph,
independence number,
lower bound
Related subjects:
Computer sciences,
Computer sciences, other

© 2014 Tariq A. Chishti, Guofei Zhou, Shariefuddin Pirzada, Antal Iványi, published by Sapientia Hungarian University of Transylvania
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Previous articleVolume 6 (2014): Issue 1 (June 2014)