 |
Combinatorial problems with an emphasis on games
|
Help 
Print 
|
Here you can view and search the projects funded by NKFI since 2004
Back »
|
| |
Details of project |
|
|
| Identifier |
116095 |
| Type |
SNN |
| Principal investigator |
Tuza, Zsolt |
| Title in Hungarian |
Kombinatorikus problémák középpontban a játékokkal |
| Title in English |
Combinatorial problems with an emphasis on games |
| Keywords in Hungarian |
dominálási játék, szaturáló játék, ládapakolási játék, gráfok és hipergráfok dominálása |
| Keywords in English |
domination game, saturation game, bin-packing game, domination of graphs and hypergraphs |
| Discipline |
| Mathematics (Council of Physical Sciences) | 100 % | | Ortelius classification: Discrete mathematics |
|
| Panel |
Mathematics and Computing Science |
| Department or equivalent |
Alfréd Rényi Institute of Mathematics |
| Participants |
Bujtás, Csilla
Dósa, György
Patkós, Balázs
Vizer, Máté
|
| Starting date |
2015-09-01 |
| Closing date |
2019-02-28 |
| Funding (in million HUF) |
24.912 |
| FTE (full time equivalent) |
7.97 |
| state |
closed project |
Summary in Hungarian A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
Alapvető és alkalmazásokhoz is szorosan kapcsolódó gráf- és hipergráfparamétereket vizsgálunk, ezeknek a kétszemélyes játékváltozatait is tekintve.
Maga a dominálás, csúcslefogás illetve a független halmaz fogalma már klasszikusnak számít a gráfelméletben és egyre intenzívebben tanulmányozott a halmazrendszerekre vonatkozóan is. Egyik célunk az, hogy a megfelelő paraméterekre korábban bizonyított korlátokat javítsuk és újabb összefüggéseket mutassunk ki a paraméterek nagysága és a tekintett gráf (hipergráf) struktúrája között. Megközelítésünk részben algoritmikus jellegű, ezért hatékonyabb approximációs eljárásokat illetve az ismert eljárások approximációs hányadosának pontosabb elemzését is reméljük.
A játékok tanulmányozása önmagában is érdekes és egyre fontosabb terület a kombinatorikában, ahol mind az általános elméletben (például a pozíciós játékok terén), mind a konkrét változatokra vonatkozóan sok nyitott probléma van még. Úgy reméljük, hogy a közös munka eredményeképpen ezek közül többet is meg tudunk majd válaszolni.
A játékváltozat tanulmányozásával a megfelelő “klasszikus” tulajdonság természetét is jobban megismerjük, ugyanakkor természetes módon alkalmazzuk az utóbbi területen elért eredményeket a játékok vizsgálatánal. Továbbá, az eddigi tapasztalataink azt mutatják, hogy például a dominálási játék kapcsán bevezetett algoritmikus bizonyítási módszer a dominálási számra vonatkozó korábbi korlátok javítására is alkalmas. Kiemelt célunk, hogy ezt a kölcsönösen inspiratív kapcsolatot kihasználva mindkét oldalon új eredményeket érjünk el.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
Matematikai kutatás esetén nehéz előre megjósolni az eredmények pontos jellegét és azt is, hogy egy bizonyos kérdést meg tudunk-e válaszolni a kutatás végén. Mindenesetre megpróbálunk néhány olyan alapvető kérdést felsorolni, amelyek vizsgálatával foglalkozni fogunk:
• Pozíciós játékok esetén elméleti kihívásnak és gyakorlati szempontból is fontosnak tartjuk az “okos” (optimális stratégia szerint játszó) és a “random” (véletlenszerűen választó) játékosok által játszott változat elemzését.
• A játék dominálási számra vonatkozó sejtés szerint két “okos” (de ellentétes célokkal bíró) fél játéka bármely n csúcsot tartalmazó (izolált csúcs nélküli) gráfban legfeljebb 3n/5 lépésben véget ér. Célunk a sejtés (részleges vagy teljes) igazolása/cáfolása, illetve olyan gráfosztályok azonosítása, ahol ennél kisebb lépésszámot tudunk garantálni, valamint a megfelelő paraméterre extremális és a kritikus hálózatok felderítése.
• A játékelméleti megközelítést szeretnénk kiterjeszteni más gráfparaméterekre is, vizsgálni szándékozunk ezen játékok egymáshoz való viszonyát, mind rögzített gráfokra, mind alkalmasan választott gráfosztályokon.
• A halmazrendszerek vagyis hipergráfok a gráf fogalmának általánosításaként tekinthetők. Más szempontból is találunk szoros kapcsolatot a megfelelő gráf- és hipergráf-paraméterek között, például egy gráf domináló halmaza megfelel az úgynevezett zárt környezeti hipergráfban vett csúcslefogó halmaznak. Fontosnak tartjuk annak vizsgálatát, hogy a gráfokra bizonyított összefüggések valamilyen általánosabb formában helytállóak maradnak-e uniform hipergráfok esetén is.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
A projekt során matematikai alapkutatásokat végzünk. A vizsgálandó problémák nemzetközi szinten fontosak, amit az elmúlt időszakra vonatkozó bibliográfiai adataink és eddigi eredményeink fogadtatása egyaránt igazol. A tekintett problémák központiak a kombinatorikában, és ugyanakkor más tudományterületeken is alkalmazásra kerülnek. Példaként említhetjük, hogy a játékelmélet a közgazdaságtan alapvető részévé vált. Ugyanakkor a domináló halmazok természetes módon interpretálhatóak közösségi hálózatokban és szenzorhálózatokban is, utóbbiakban a kommunikációért felelős fő szenzoroknak felelnek meg; a k-dominálás ezen alkalmazásoknak a legfeljebb (k-1)-szeres meghibásodást toleráló változata. Az elektromos („power”) dominálás fogalma pedig közvetlenül abból az optimalizálási problémából ered, amelyben egy elektromos ellátó rendszert kell minél kevesebb mérőeszköz segítségével felügyelni. Ily módon a vizsgálni tervezett területeken elérendő eredményeknek igen szerteágazó tudományos és gyakorlati hatása lehet.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A kombinatorikus problémák mindenhol jelen vannak életünkben. Ez az oka annak, hogy e terület tanulmányozásának történelmi gyökerei oly messzire nyúlnak vissza. A számítógépek gyors fejlődése által a kombinatorikus matematika szerepe tovább növekedett és az egyik legintenzívebben kutatott matematikai területté vált. A tendencia alapján a XXI. században az optimalizálási problémák – köztük a kombinatorikusak – és megoldásuk fontosabb, mint valaha: egy jobb megoldás segítségével pénzt, energiát, időt takaríthatunk meg, és a természeti környezet védelmét is szolgálhatja. A számítógépek teljesítményének növekedése lehetővé teszi, hogy olyan optimális vagy optimum-közeli megoldásokat találjunk, amelyek korábban nem voltak elérhetőek. A fő tényező azonban az emberi értelem marad, amely képes kapcsolatot teremteni egymástól távol eső és elvont fogalmak között is, sejtéseket fogalmaz meg, állításokat igazol „hideg” szigorúan logikai alapon, és algoritmusokat tervez azért, hogy jobb megoldásokhoz jussunk rövidebb időn belül.
Amikor a gráfokat és a halmazrendszereket, azon belül a dominálási és a kapcsolódó optimalizálási problémákat tanulmányozzuk, olyan absztrakt entitásokkal foglalkozunk, amelyek sok gyakorlati probléma modelljéül szolgálhatnak.
Eredményeinket vezető diszkrét matematikai szakfolyóiratokban tervezzük pulikálni, és szándékozunk beszámolni róluk nemzetközi tudományos konferenciákon is. Úgy reméljük, plenáris előadások tartására is meghívást fogunk kapni, ami szintén hangsúlyozza a projekt során elért eredmények fontosságát. Mindezek által tovább növekedhet mind a magyar, mind a szlovén diszkrét matematikai iskola tudományos elismertsége.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
We study fundamental graph and hypergraph parameters which are closely related to applications, too. We also consider their 2-person-game versions.
The notions of domination, vertex cover, and independent set are already classical in graph theory, and they are investigated more and more intensively also for set systems. One of our goals is to improve the bounds proved earlier on the corresponding parameters, and to point out new relations between their values and the structure of the graph (hypergraph) under consideration. Our approach partly has an algorithmic character, therefore we also hope to obtain more efficient approximation procedures and a more accurate analysis of the approximation ratios of some known algorithms.
The study of games is interesting in its own right, and also is increasingly important in combinatorics. Still there are many open problems in the general theory (e.g. in the area of positional games) and concerning explicit versions of games, too. We hope to answer a number of those questions as a result of the proposed joint work.
The study of the game version leads to a better understanding of the characteristics of the corresponding “classical” property and, at the same time, results achieved in the latter area can be applied in a natural way in the research on games. Moreover, our experience shows for instance that the algorithmic proof method developed for the domination game can also be applied for improving earlier bounds on the domination number. One of our goals with priority is to benefit from this mutually inspirational connection in order to achieve new results on both sides.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
In mathematical research it is difficult to predict the exact type of results and whether a certain question can be answered at the end of the study. Nevertheless, we list some important directions which we will investigate.
• Concerning positional games we find it both a theoretical challenge and a matter of practical importance to analyze the game played by a “clever” player (applying an optimal strategy) against a “random” one (playing according to a probabilistic model).
• A conjecture on the game domination number states that the game of two “clever” players (whose goals are opposite) ends in at most 3n/5 moves on every graph with n vertices (if isolated vertices are excluded). Our goal is to prove (partially or completely) or disprove this conjecture and to identify classes of graphs where a smaller number of moves can be guaranteed, moreover to describe networks which are extremal or critical for the corresponding parameter.
• We would like to extend the game-theoretic approach to further invariants of graphs. We wish to study the relation of those games to each other, on fixed graphs and also on suitably chosen graph classes.
• Set systems, i.e. hypergraphs, can be viewed as generalizations of graphs. We can find close connections between various graph and hypergraph invariants from another perspective, too; for instance, a dominating set in a graph corresponds to a vertex cover in the so-called closed neighborhood hypergraph. We consider it important to study whether the properties and formulas proved for graphs remain valid more generally in uniform hypergraphs, too.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
The project belongs to basic research in the area of mathematics. Problems that we will work on are internationally important, which can in particular be justified by our bibliography from the last period, as well as with the impact of our results. The problems are central in the area of combinatorics and at the same time they have applications in other scientific fields. For instance, game theory is ubiquitous in economics. Dominating set has a natural interpretation in social networks and also in sensor networks where dominating set represents the set of head sensors being responsible for the communication; the k-domination is just the (k-1)-fault-tolerant version of these applications. The notion of power domination came directly from the optimization problem where we want to monitor an electric power system by using as few measurement devices as possible. In this way, results obtained on the areas planned to study may have impact on very different areas of science and practice.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Combinatorial problems are intrinsic in our lives. This is the reason that the historical roots of this research area go back so far. The fast development of computers led the investigations in combinatorial mathematics to be one of the central subjects and one of the most explored mathematical topics. Trends indicate that, in the 21st century, optimization problems—including the discrete ones—and their solutions are more important than ever: a better solution may mean saving money, energy, time and also saving the natural environment. The capacity of computers allows us to get optimal solutions or better approximations than we had earlier, but the main factor remains the human mind who establishes connections between distant and abstract concepts, or formulates conjectures, proves statements in a „cold” strictly logical way and designs algorithms for obtaining better solutions in shorter time.
When studying graphs and set systems, in particular domination and related optimization problems in combinatorial structures, we are working with highly abstract entities which can serve as models for many practical problems.
We expect that the newly obtained results will be published in leading journals in the area of discrete mathematics, and we will present them at international scientific conferences. We also expect that we will be invited to deliver invited plenary talks which will further emphasize the importance of our research achievements. In this way we would further increase the international role of the Hungarian and the Slovenian school in discrete mathematics.
|
|
|
|
|
|
|
|
| |
List of publications |
|
|
| G. Dosa, Zs. Tuza: Multiprofesor Scheduling, Discrete Applied Mathematics, 234, 195-209, 2018 | | G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, Theoretical Computer Science, 760, 72-87, 2019 | | Cs. Bujtás, M. Jakovac: Relating the total domination number and the annihilation number of cactus cactus graphs and block graphs, Ars Mathematica Contemporanea 16:1 183-202, 2019 | | Zs. Tuza: Mixed hypergraphs and beyond, The Art of Discrete and Applied Mathematics, accepted, 2018 | | Gy. Dosa, L. Epstein: Quality of strong equilibria for selfish bin packing with uniform cost sharing, Journal of Scheduling, in print, DOI: 10.1007/s10951-018-0587-8, 2018 | | Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, Journal of Combinatorial Optimization, 37:3, 827-847, 2019 | | D. Gerbner, B. Patkós, M. Vizer: Forbidden subposet problems for traces of set families, Electronic Journal of Combinatorics, 25:3, P3.49, 2018 | | D. Gerbner, M. Vizer: Majority problems of large query size, Discrete Applied Mathematics, 254, 124-134, 2019 | | D. Gerbner, M.Vizer: Smart elements in combinatorial group testing problems with more defectives, The Art of Discrete and Applied Mathematics, accepted, 2017 | | D. Gerbner, D. Lenger, M. Vizer: A plurality problem with three colors and query size three, Proceedings of 11th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, accepted, 2017 | | D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, M. Vizer: An improvement on the maximum number of k-dominating independent sets, Journal of Graph Theory, in print, DOI: 10.1002/jgt.22422, 2018 | | Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: Domination game on uniform hypergraphs, Discrete Applied Mathematics, 258, 65-75, 2019 | | B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: On Grundy total domination number in product graphs,, Discussiones Mathematicae Graph Theory, in print, DOI: 10.7151/dmgt.2184, 2018 | | Gy. Dósa, H. Kellerer, Zs. Tuza: Bin packing games with weight decision: how to get a small value for the Price of Anarchy, In: Epstein L., Erlebach T. (eds), Approximation and Online Algorithms. WAOA 2018, Lecture Notes in Computer Science, 11312, pp. 204-217, 2018 | | J. Balogh, J. Békési, Gy. Dósa, L. Epstein, A. Levin: Lower Bounds for Several Online Variants of Bin Packing, Theory of Computing Systems, in print, DOI: 10.1007/s00224-019-09915-1, 2019 | | J. Balogh, J. Békési, Gy. Dósa, J. Sgall, R. van Stee: The optimal absolute ratio for online bin packing, Journal of Computer and System Sciences, 102, 1-17, 2019 | | Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight lower bounds for semi-online scheduling on two uniform machines with known optimum, European Journal of Operations Research, in print, DOI: 10.1007/s10100-018-0536-9, 2018 | | R. B. Bapat, S. Fujita, S. Legay, Y. Manoussakis, Y. Matsui, T. Sakuma, Zs. Tuza: Safe sets, network majority on weighted trees, Networks. 71, 81-92., 2018 | | R. Águeda, N. Cohen, S. Fujita, S. Legay, Y. Manoussakis, Y. Matsui, L. Montero, R. Naserasr, H. Ono, Y. Otachi, T. Sakuma, Zs. Tuza, R. Xu: Safe sets in graphs: Graph classes and structural parameters, Journal of Combinatorial Optimization, 36:4, 1221-1242, 2018 | | G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Zs. Tuza, E. J. van Leeuwen: Subexponential-time algorithms for Maximum Independent Set in Pt-Free and broom-free graphs, Algorithmica, 81:2, 421–438, 2019 | | C. Bazgan, H. Fernau, Zs. Tuza: Aspects of upper defensive alliances, Discrete Applied Mathematics, in print, DOI: 10.1016/j.dam.2018.05.061, 2018 | | L. Badakhshian, G. O. H. Katona, Zs. Tuza: The domination number of the graph defined by two levels of the n-cube, Discrete Applied Mathematics, in print, DOI: 10.1016/j.dam.2019.02.006, 2019 | | C. Bazgan, T. Pontoizeau, Zs. Tuza: Finding a potential community in networks, Theoretical Computer Science, 769, 32-42, 2019 | | G. Bacsó, Cs. Bujtás, C. Tompkins, Zs. Tuza: Disjoint paired-dominating sets in cubic graphs, submitted manuscript, 2018 | | S. Cichacz, A. Görlich, Zs. Tuza: Z2xZ2-cordial cycle-free hypergraphs, submitted manuscript, 2018 | | M. Gionfriddo, L. Milazzo, Zs. Tuza: Hypercycle systems, submitted manuscript, 2018 | | Zs. Tuza: Graph labeling games, Electronic Notes in Discrete Mathematics, 60, 61-68, 2017 | | Cs. Bujtás, Zs. Tuza: Partition-crossing hypergraphs, Acta Cybernetica, 23:3, 815-828, 2018 | | G. Boruzanli Ekinci, Cs. Bujtás: On the equality of domination number and 2-domination number, submitted manuscript, 2018 | | D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, M. Vizer: An improvement on the maximum number of k-dominating independent sets, submitted manuscript, 2017 | | Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: Domination game on uniform hypergraphs, submitted manuscript, 2017 | | D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: Forbidding rank-preserving copies of a poset, submitted manuscript, 2017 | | B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: On Grundy total domination number in product graphs,, submitted manuscript, 2017 | | D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: On the number of containments in P-free families, submitted manuscript, 2017 | | D. Gerbner, A. Methuku, D. Nagy, B. Patkós, M. Vizer: Stability results on vertex Turán problems in Kneser graphs, submitted manuscript, 2018 | | D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: Vertex Turán problems for the oriented hypercube, submitted manuscript, 2018 | | E. Győri, D. Korándi, A. Methuku, I. Tomon, C. Tompkins, M. Vizer: On the Turán number of some ordered even cycles, European Journal of Combinatorics, 73, 81-88, 2018 | | E. Győri, A. Methuku, N. Salia, C. Tompkins, M. Vizer: On the maximum size of connected hypergraphs without a path of given length, Discrete Mathematics, 341:9, 2602-2605, 2018 | | D. Gerbner, A. Methuku, M. Vizer: Generalized Turán problems for disjoint copies of graphs, submitted manuscript, 2018 | | D. Gerbner, E. Győri, A. Methuku, M. Vizer: Generalized Turán problems for even cycles, submitted manuscript, 2018 | | G. Kiss, R. D. Malikiosis, G. Somlai, M. Vizer: On the discrete Fuglede and Pompeiu problems, submitted manuscript, 2018 | | D. Gerbner, A. Methuku, G. Omidi, M. Vizer: Ramsey problems for Berge hypergraphs, submitted manuscript, 2018 | | Gy. Dósa: The Intermediate Price of Anarchy (IPoA) in bin packing games, Discrete Applied Mathematics 242, 16-25, 2018 | | Gy. Dósa, L. Epstein: The tight asymptotic approximation ratio of First Fit for bin packing with cardinality constraints, Journal of Computer and System Sciences, 96, 33-49, 2018 | | Gy. Dósa, H. Kellerer, Zs. Tuza: Bin packing games with weight decision: how to get a small value for the Price of Anarchy, Proceedings of WAOA 2018, Lecture Notes in Computer Science, accepted, 2018 | | K. Bérczi, A. Bernáth, M. Vizer: Regular graphs are antimagic, Electronic Journal of Combinatorics, 22:3, P3.34, 2015 | | E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Proceedings of Graph Drawing '16, Lecture Notes in Computer Science, 9801, in print, 2016 | | E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Proceeding of SoCG 2016 (32nd International Symposium on Computational Geometry), LIPIcs – Vol. 51, pp. 5:1-5:16, 2016 | | S. Aparna Lakshmanan, Cs. Bujtás, Zs. Tuza: Induced cycles in triangle graphs, Discrete Applied Mathematics, 209, 264-275, 2016 | | Cs. Bujtás, Gy. Dosa, Cs. Imreh, J. Nagy-György, Zs. Tuza: New models of Graph-Bin Packing, Theoretical Computer Science, 640:9, 94--103, 2016 | | Cs. Bujtás, M.A. Henning, Zs. Tuza: Transversal game on hypergraphs and the 3/4-Conjecture on the total domination game, SIAM Journal on Discrete Mathematics, 2016 | | Cs. Bujtás, M.A. Henning, and Zs. Tuza: Bounds on the game transversal number in hypergraphs, European Journal of Combinatorics, 59, 34-50, 2017 | | G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, in press, 2016 | | G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, MATCOS 16, Middle-European Conference on Applied Theoretical Computer Science, accepted, 2016 | | D. Gerbner, M. Vizer: A note on tilted Sperner families, Discrete Mathematics, accepted, 2016 | | Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, submitted manuscript, 2016 | | Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: The minimum number of vertices in uniform hypergraphs with given domination number, submitted manuscript, 2016 | | B. Bresar, Cs. Bujtás, T. Gologranc, S. Klavzar, G. Kosmrlj, B. Patkós, Zs. Tuza, M. Vizer: Dominating sequences in grid-like and toroidal graphs, submitted manuscript, 2016 | | G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, submitted manuscript, 2016 | | D. Gerbner, B. Keszegh, G. Mészáros, B. Patkós, M. Vizer: Line percolation in finite projective planes, submitted manuscript, 2016 | | D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Finding a majority ball with majority answers, submitted manuscript, 2016 | | K. Bérczi, A. Bernáth, M. Vizer: Regular graphs are antimagic, Electronic Journal of Combinatorics, 22:3, P3.34, 2015 | | E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Journal of Graph Algorithms and Applications (accepted), 2017 | | E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Discrete and Computational Geometry (accepted), 2017 | | Cs. Bujtás, Gy. Dosa, Cs. Imreh, J. Nagy-György, Zs. Tuza: New models of Graph-Bin Packing, Theoretical Computer Science, 640:9, 94-103, 2016 | | Cs. Bujtás, M.A. Henning, Zs. Tuza: Transversal game on hypergraphs and the 3/4-Conjecture on the total domination game, SIAM Journal on Discrete Mathematics, 30:3, 1830-1847, 2016 | | G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, in press, 2017 | | G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, Middle-European Conference on Applied Theoretical Computer Science MATCOS 16, 12-13 October 2016, Proceedings of the 19th International Multiconference INFORMATION SOCIET, 2016 | | D. Gerbner, M. Vizer: A note on tilted Sperner families with patterns, Discrete Mathematics, 339:11, 2737-2741, 2016 | | Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, Combinatorics, Probabilty and Computing (accepted), 2016 | | Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: The minimum number of vertices in uniform hypergraphs with given domination number, Discrete Mathematics, 340:11, 2704-2713, 2017 | | B. Bresar, Cs. Bujtás, T. Gologranc, S. Klavzar, G. Kosmrlj, B. Patkós, Zs. Tuza, M. Vizer: Dominating sequences in grid-like and toroidal graphs, Electronic Journal of Combinatorics, 23:4, #P4.34, 19 pp., 2016 | | Cs. Bujtás, Sz. Jaskó: Bounds on the 2-domination number, Discrete Applied Mathematics, in press, 2017 | | Cs. Bujtás, M. Jakovac: Relating the total domination number and the annihilation number of cactus and block graphs, submitted manuscript, 2017 | | Cs. Bujtás: On the game total domination number, submitted manuscript, 2017 | | Cs. Bujtás, Zs. Tuza: F-WORM colorings: Results for 2-connected graphs, Discrete Applied mathematics, 231, 131-138, 2017 | | Z. Wang, X. Han, Gy. Dósa, Zs. Tuza: A general bin packing game: Interest taken into account, Algorithmica, in press, 2017 | | Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Central European Journal of Operations Research, in press, 2017 | | J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Lower bounds for several online variants of bin packing, 15th Workshop on Approximation and Online Algorithms (WAOA 2017), 7-8 September 2017. Vienna, Austria (WAOA), accepted, 2017 | | J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: A new and improved algorithm for online bin packing, submitted manuscript, 2017 | | J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Online bin packing with cardinality constraints resolved, ESA 2017 – The 25th Annual European Symposium on Algorithms (ALGO 2017 September 4-8, Vienna, Austria), accepted, 2017 | | Gy. Dosa, L. Epstein: The convergence time for selfish bin packing, submitted manuscript, 2017 | | Gy. Dosa, L. Epstein: Selfish bin packing with general weights, submitted manuscript, 2017 | | Gy. Dosa, L. Epstein: Quality of strong equilibria for selfish bin packing with uniform cost sharing, submitted manuscript, 2017 | | Gy. Dosa, L. Epstein: The price of anarchy for selfish bin packing with uniform cost sharing, submitted manuscript, 2017 | | Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, submitted manuscript, 2017 | | D. Gerbner, B. Patkós, M. Vizer: Forbidden subposet problems for traces of set families, submitted manuscript, 2017 | | D. Gerbner, B. Keszegh, B. Patkos: Generalized forbidden subposet problems, submitted manuscript, 2017 | | D. Gerbner, B. Keszegh, C. Palmer, B. Patkós: On the number of cycles in a graph with restricted cycle lengths, SIAM Journal on Discrete Mathematics (accepted), 2017 | | B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza, M. Vizer: Grundy dominating sequences and zero forcing sets, Discrete optimization, in press, 2017 | | M. Rahman, B. Virág, M. Vizer: Geometry of permutation limits, submitted manuscript, 2017 | | D. Gerbner, M. Vizer: Majority problems of large query size, submitted manuscript, 2017 | | D. Gerbner, M. Vizer: Rounds in a combinatorial search problem, submitted manuscript, 2017 | | D. Gerbner, M.Vizer: Conscious and controlling elements in combinatorial group testing problems, submitted manuscript, 2017 | | D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, submitted manuscript, 2017 | | D. Gerbner, M. Vizer: Conscious and controlling elements in combinatorial group testing problems with more defectives, submitted manuscript, 2017 | | D. Gerbner, D. Lenger, M. Vizer: A plurality problem with three colors and query size three, submitted manuscript, 2017 | | E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Journal of Graph Algorithms and Applications, 22:1, 11-22, 2018 | | E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Discrete & Computational Geometry, 58:4, 757-784, 2017 | | G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, 234, 195-209, 2018 | | G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, Middle-European Conference on Applied Theoretical Computer Science MATCOS 16, 12-13 October 2016, Proc. 19th International Multiconference INFORMATION SOCIETY, pp. 80-82, 2016 | | Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, Combinatorics, Probabilty and Computing, 27:1, 1-20, 2018 | | G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, Theoretical Computer Science, in print, https://doi.org/10.1016/j.tcs.2018.08.016, 2017 | | D. Gerbner, B. Keszegh, G. Mészáros, B. Patkós, M. Vizer: Line percolation in finite projective planes, SIAM Journal on Discrete Mathematics, 32:2, 864-881, 2018 | | D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Finding a non-minority ball with majority answers, Discrete Applied Mathematics, 219:11, 18-31, 2017 | | Cs. Bujtás, Sz. Jaskó: Bounds on the 2-domination number, Discrete Applied Mathematics, 242, 4-15, 2018 | | Cs. Bujtás: On the game total domination number, Graphs and Combinatorics, 34:3, 415-425, 2018 | | Z. Wang, X. Han, Gy. Dósa, Zs. Tuza: A general bin packing game: Interest taken into account, Algorithmica, 80:5, 1534–1555, 2018 | | Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Central European Journal of Operations Research, 26:1, 161–180, 2018 | | J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Lower bounds for several online variants of bin packing, 15th Workshop on Approximation and Online Algorithms (WAOA 2017), 7-8 September 2017. Vienna, Austria (WAOA), Lecture Notes in Computer Science, 10787, 102-117, 2017 | | J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Online bin packing with cardinality constraints resolved, submitted manuscript, 2017 | | Gy. Dosa, L. Epstein: The convergence time for selfish bin packing, Acta Cybernetica, 23, 853–865, 2018 | | Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, Journal of Combinatorial Optimization, in print, https://doi.org/10.1007/s10878-018-0323-5, 2018 | | D. Gerbner, B. Keszegh, C. Palmer, B. Patkós: On the number of cycles in a graph with restricted cycle lengths, SIAM Journal on Discrete Mathematics, 32:1, 266-279, 2018 | | B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza, M. Vizer: Grundy dominating sequences and zero forcing sets, Discrete optimization, 26, 66-77, 2017 | | M. Rahman, B. Virág, M. Vizer: Geometry of permutation limits, Combinatorica, accepted, 2017 | | D. Gerbner, M. Vizer: Majority problems of large query size, Discrete Applied Mathematics, in print, https://www.sciencedirect.com/science/article/pii/S0166218X18303512, 2018 | | D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, Journal of Combinatorial Theor Ser. B, accepted, 2017 | | D. Gerbner, M. Vizer: Smart elements in combinatorial group testing problems, Journal of Combinatorial Optimization, 35:4, 1042-1060, 2018 |
|
|
|
|
|
|
|
|
|
