Discrete mathematical models related to problems in informatics  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
49613
Type K
Principal investigator Tuza, Zsolt
Title in Hungarian Műszaki informatikai problémákhoz kapcsolódó diszkrét matematikai modellek vizsgálata
Title in English Discrete mathematical models related to problems in informatics
Panel Informatics and Electrical Engineering
Department or equivalent Department of Computer Science and Systems Technology (University of Pannonia)
Participants Bacsó, Gábor
Bujtás, Csilla
Szoldatics, József
Starting date 2005-01-01
Closing date 2008-12-31
Funding (in million HUF) 11.962
FTE (full time equivalent) 3.76
state closed project





 

Final report

  
Results in Hungarian
Diszkrét matematikai módszerekkel strukturális és kvantitatív összefüggéseket bizonyítottunk; algoritmusokat terveztünk, komplexitásukat elemeztük. Az eredmények a gráfok és hipergráfok elméletéhez, valamint on-line ütemezéshez kapcsolódnak. Néhány kiemelés: - Pontosan leírtuk azokat a szerkezeti feltételeket, amelyeknek teljesülni kell ahhoz, hogy egy kommunikációs hálózatban és annak minden összefüggő részében legyen olyan, megadott típusú összefüggő részhálózat, ahonnan az összes többi elem közvetlenül elérhető. (A probléma két évtizeden át megoldatlan volt.) - Aszimptotikusan pontos becslést adtunk egy n-elemű alaphalmaz olyan, k-asokból álló halmazrendszereinek minimális méretére, amelyekben minden k-osztályú partícióhoz van olyan halmaz, ami az összes partíció-osztályt metszi. (Nyitott probléma volt 1973 óta, több szerző egymástól függetlenül is felvetette.) - Halmazrendszerek partícióira az eddigieknél általánosabb modellt vezettünk be, megvizsgáltuk részosztályainak hierarchikus szerkezetét és hatékony algoritmusokat adtunk. (Sok alkalmazás várható az erőforrás-allokáció területén.) - Kidolgoztunk egy módszert, amellyel lokálisan véges pozíciós játékok nyerő stratégiája megtalálható mindössze lineáris méretű memória használatával. - Félig on-line ütemezési algoritmusokat terveztünk (kétgépes feladatra, nem azonos sebességű processzorokra), amelyeknek versenyképességi aránya bizonyítottan jobb, mint ami a legjobb teljesen on-line módszerekkel elérhető.
Results in English
Applying discrete mathematical methods, we proved structural and quantitative relations, designed algorithms and analyzed their complexity. The results deal with graph and hypergraph theory and on-line scheduling. Some selected ones are: - We described the exact structural conditions which have to hold in order that an intercommunication network and each of its connected parts contain a connected subnetwork of prescribed type, from which all the other nodes of the network can be reached via direct link. (This problem was open for two decades.) - We gave asymptotically tight estimates on the minimum size of set systems of k-element sets over an n-element set such that, for each k-partition of the set, the set system contains a k-set meeting all classes of the partition. (This was an open problem since 1973, raised by several authors independently.) - We introduced a new model, more general than the previous ones, for partitions of set systems. We studied the hierarchic structure of its subclasses, and designed efficient algorithms. (Many applications are expected in the area of resource allocation.) - We developed a method to learn winning strategies in locally finite positional games, which requires linear-size memory only. - We designed semi-online scheduling algorithms (for two uniform processors of unequal speed), whose competitive ratio provably beats the best possible one achievable in the purely on-line setting.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=49613
Decision
Yes





 

List of publications

  
Dominich S., Skrop A., Tuza Zs.: Formal theory of connectionist web retrieval, Soft Computing in Web Information Retrieval: Techniques and Applications. Studies in Fuzziness and Soft Computing Vol. 197, Springer-Verlag, pp. 163-194, 2006
Bujtás Cs., Tuza Zs.: Mixed colorings of hypergraphs, Electronic Notes in Discrete Mathematics 24, 273-275, 2006
Angelelli E., Speranza M. G., Tuza Zs.: New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks, Discrete Mathematics and Theoretical Computer Science 8 (1), 1-15, 2006
Tuza Zs.: Highly connected counterexamples to a conjecture on a-domination, Discussiones Mathematicae Graph Theory 25 (3), 435–440, 2005
Bujtás Cs., Tuza Zs.: Color-bounded hypergraphs. III. Model comparison, Applicable Analysis and Discrete Mathematics 1 (1), 36-55, 2007
Bacsó G., Tuza Zs.: The cost chromatic number and hypergraph parameters, Discussiones Mathematicae Graph Theory 26 (3), 369-376, 2006
Tuza Zs.: Steiner systems and large non-Hamiltonian hypergraphs, Le Matematiche LXI (Fasc. I), 179-183, 2006
Borowiecki M., Sidorowicz E., Tuza Zs.: Game list colouring of graphs, Electronic Journal of Combinatorics 14 (1), R26, 11 pp., 2007
Deogun J. S., Tuza Zs.: Graph-theoretic methods and recent applications in computer science, Formal Methods in Computing (M. Ferenczi et al., eds.), Akadémiai Kiadó, 55-96, 2005
Tuza Zs.: Extremal jumps of the Hall number, Electronic Notes in Discrete Mathematics, 28, 83-89, 2007
Bujtás Cs., Tuza Zs.: Orderings of uniquely colorable hypergraphs, Discrete Applied Mathematics 155 (11), 1395-1407, 2007
Horňák M., Tuza Zs., Wożniak M.: On-line arbitrarily vertex decomposable trees, Discrete Applied Mathematics 155 (11), 1420-1429, 2007
Bacsó G.: Perfectly orderable graphs and unique colorability, Applicable Analysis and Discrete Mathematics 1 (2), 415-419, 2007
Milazzo L., Tuza Zs.: A class of Steiner systems S(2,4,v) with arcs of extremal size, Tatra Mountains Mathematical Publications 36, 153-162, 2007
Bacsó G., Tuza Zs.: Upper chromatic number of finite projective planes, Journal of Combinatorial Designs 16 (3), 221-230, 2008
Tuza Zs., Voloshin V.: Problems and results on colorings of mixed hypergraphs, Horizon of Combinatorics, Bolyai Society Mathematical Studies Vol. 17, Springer-Verlag, 235-255, 2008
Angelelli E., Speranza M. G., Tuza Zs.: Semi-online scheduling on two uniform processors, Theoretical Computer Science 393 (1-3), 211-219, 2008
Bacsó G., Bujtás Cs., Tuza Zs., Voloshin V.: New challenges in the theory of hypergraph coloring, Proceedings of ICDM'08, International Conference on Discrete Mathematics, Mysore, India, pp. 67-78, 2008
Bazgan C., Tuza Zs.: Combinatorial 5/6-approximation of Max Cut in graphs of maximum degree 3, Journal of Discrete Algorithms 6 (3), 510-519, 2008
Bazgan C., Tuza Zs., Vanderpooten D.: Approximation of satisfactory bisection problems, Journal of Computer and System Sciences 74 (5), 875-883, 2008
Bujtás Cs., Tuza Zs.: Uniform mixed hypergraphs: The possible numbers of colors, Graphs and Combinatorics 24 (1), 1-12, 2008
Caro Y., Lev A., Roditty Y., Tuza Zs., Yuster R.: On rainbow connection, Electronic Journal of Combinatorics 15 (1), #R57, 2008
Tuza Zs.: Hereditary domination in graphs: Characterization with forbidden induced subgraphs, SIAM Journal on Discrete Mathematics 22 (3), 849-853, 2008
Fernandez de la Vega W., Tuza Zs.: Groupies in random graphs, Information Processing Letters 109 (7), 339-340, 2009
Angelelli E., Speranza M. G., Szoldatics J., Tuza Zs.: Geometric representation for semi on-line scheduling on uniform processors, Optimization Methods and Software (accepted), 2009
Bacsó G.: Complete description of forbidden subgraphs in the structural domination problem, Discrete Mathematics, http://dx.doi.org/10.1016/j.disc.2008.05.053 (in print), 2009
Bacsó G., Bujtás Cs., Tuza Zs., Voloshin V.: Hypergraph coloring: New kinds of problems, Proceedings of Midsummer Combinatorial Workshop, Praha, 2008, Charles University (in print), 2009
Böhme Th., Göring F., Tuza Zs., Unger H.: Learning of winning strategies for terminal games with linear-size memory, International Journal of Game Theory, doi: 10.1007/s00182-008-0142-5 (in print), 2009
Bujtás Cs., Tuza Zs.: Color-bounded hypergraphs, I: General results, Discrete Mathematics, doi:10.1016/j.disc. 2008.04.019 (in print), 2009
Bujtás Cs., Tuza Zs.: Color-bounded hypergraphs, II: Interval hypergraphs and hypertrees, Discrete Mathematics, doi:10.1016/j.disc.2008.10.023 (in print), 2009
Bujtás Cs., Tuza Zs.: Coloring intervals with four types of constraints, Proceedings of the Sixth Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (accepted), 2009
Chartrand G., Okamoto F., Tuza Zs., Zhang P.: A note on graphs with prescribed complete coloring numbers, Journal of Combinatorial Mathematics and Combinatorial Computing (accepted), 2009
Hangos K. M., Tuza Zs., Yeo A.: Some complexity problems on Single Input Double Output controllers, Discrete Applied Mathematics, doi:10.1016/j.dam.2008.03.028 (in print), 2009
Milazzo L., Tuza Zs.: Logarithmic upper bound for the upper chromatic number of S(t,t+1,v) systems, Ars Combinatoria 92, 2009 (in print), 2009
Novák Á. B., Tuza Zs.: Extending the spatial relational model PLA to represent trees, Intelligent Engineering Systems and Computational Cybernetics (Teneiro Machado J. A., Pátkai B., eds.), Springer-Verlag, ISBN: 978-1-4020-8677-9 (in print), 2009
Stiebitz M., Tuza Zs., Voigt M.: On list critical graphs, Discrete Mathematics, doi: 10.1016/j.disc.2008.05.021 (in print), 2009
Bacsó G., Jung H. A., Tuza Zs.: Infinite vs. finite graph domination, (submitted), 2010
Bacsó G., Tuza Zs.: Clique-transversal sets and weak 2-colorings in graphs of small maximum degree, (submitted), 2010
Bazgan C., Couëtoux B., Tuza Zs.: Covering a graph with a constrained forest, (submitted), 2010
Bazgan C., Tuza Zs., Vanderpooten D.: Satisfactory graph partitions and their generalizations, (submitted), 2010
Bujtás Cs., Tuza Zs.: Smallest set-transversals of k-partitions, (submitted), 2010
Bujtás Cs., Tuza Zs.: Voloshin's conjecture for C-perfect hypertrees, (submitted), 2010
Bujtás Cs., Tuza Zs.: C-perfect hypergraphs, (submitted), 2010
Bujtás Cs., Tuza Zs.: Color-bounded hypergraphs, IV: Stable colorings of hypertrees, (submitted), 2010
Dósa Gy., Speranza M. G., Tuza Zs.: Two uniform machines with nearly equal speeds: Competitive ratio of semi on-line scheduling, (submitted), 2010
Le V. B., Tuza Zs.: Finding optimal rainbow connection is hard, (submitted), 2010
Matos Camacho S., Schiermeyer I., Tuza Zs.: Approximation algorithms for the minimum rainbow subgraph problem, (submitted), 2010
Milici S., Quattrocchi G., Tuza Zs.: G-designs without blocking sets, (submitted), 2010
Tuza Zs.: Hall number for list colorings of graphs: Extremal results, (submitted), 2010
Bibin K. Jose, Tuza Zs.: Stable sets and domination in hypergraphs, (to be submitted soon), 2010
Bujtás Cs., Tuza Zs., Voloshin V.: Color-bounded hypergraphs, V: Host graphs and subdivisions, (to be submitted soon), 2010
Bujtás Cs., Sampathkumar E., Tuza Zs.: 3-consecutive C-colorings of graphs, (to be submitted soon), 2010
Frendrup A., Tuza Zs., Vestergaard P. D.: Distance domination in partitioned graphs, (to be submitted soon), 2010
Hegyháti M., Tuza Zs.: Colorability of mixed hypergraphs and their chromatic inversion, (to be submitted soon), 2010



Back »