Graphs and algoritms  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
46234
Type K
Principal investigator Grolmusz, Vince
Title in Hungarian Gráfok és algoritmusok
Title in English Graphs and algoritms
Panel Mathematics and Computing Science
Department or equivalent Department of Computer Science (Eötvös Loránd University)
Participants Friedl, Katalin
Friedman, Anna Eszter
Katona, Gyula
Király, Zoltán
Komjáth, Péter
Lukács, András
Szabadka, Zoltán
Szőnyi, Tamás
Tardos, Gábor
Windhager, Eszter
Starting date 2004-01-01
Closing date 2008-12-31
Funding (in million HUF) 22.415
FTE (full time equivalent) 0.32
state closed project





 

Final report

  
Results in Hungarian
A kutatás az elvárt eredménnyel zárult: tekintélyes nemzetközi konferenciákon és pubikációkban hoztuk nyilvánosságra az eredményéket, ideértve a STOC, SIAM és IEEE kiadványokat is, valamint egy könyvet is. A publikációk száma a matematikában elég magas (74). Ez nemzetközi összehasonlításban is kiemelkedő mutató a támogatás összegére vetítve. A projektben megmutattuk, hogy a gráfelmelet és a diszkrét matematika eszköztára számos helyen jól alkalmazható, ilyen terület a nagysebességű kommunikációs hálózatok tervezése, ezekben igen gyors routerek létrehozása. Egy másik terület a biológiai nagymolekulákon definiált gráfok és geometriai struktúrák.
Results in English
The research concluded with the awaited results: in good international conferences and journals we published 74 works, including STOC conference, SIAM conferences and journals and one of the best IEEE journal. This number is high above average in mathematics research. We showed in the project that the tools of graph theory and discrete mathematics can be well applied in the high-speed communication network design, where we proposed fast and secure routing solutions. Additionally we also found applications in biological macromolecules.
Full text http://real.mtak.hu/1348/
Decision
Yes





 

List of publications

  
Marcus, Adam; Tardos, Gábor: Excluded permutation matrices and the Stanley-Wilf conjecture., J. Combin. Theory Ser. A 107 no. 1, 153--160., 2004
Friedl, Katalin; Heged\H us, Gábor; Rónyai, Lajos: Gröbner bases for complete $l$-wide families., Publ. Math. Debrecen 70 (2007), no. 3-4, 2007
M. Kano, Katona Gyula Y., Király Zoltán: Packing paths of length at least two, Discrete Mathematics 283 pp. 129-135. (impakt faktor: 0.237), 2004
Katona Gyula Y.: Hamiltonian chains in hypergraphs - A survey, Graphs,Combinatorics, Algorithms and Applications (ed. Arumugam, Acharya, Rao), Narosa Publishing House, India, 2004
Fogaras Dániel, Lukács András: Klaszterezés. Infomatikai algoritmusok II. (alkotó szerkesztő Iványi Antal), ELTE Eötvös Kiadó, 29. Fejezet, 1409-1435., 2005
Foreman, Matthew; Komjath, Peter: The club guessing ideal: commentary on a theorem of Gitik and Shelah., J. Math. Log. 5 (2005), no. 1, 99--147., 2005
Tardos, Gábor: On 0-1 matrices and small excluded submatrices., J. Combin. Theory Ser. A 111 (2005), no. 2, 266--288., 2005
A. Lukács: Generating random elements of Abelian groups, Random Structures and Algorithms, 26 (4) 2005, 437-445., 2005
A. Dudek, Katona Gyula Y., P. A. Wojda: Hamiltonian Path Saturated Graphs with Small Size, Discrete Appl. Math. 154 (2006), no. 9, 1372--1379., 2006
Grolmusz, Vince: Co-Orthogonal Codes, Designs, Codes and Cryptography, Vol. 38, No. 3 (2006) pp. 363-372, 2006
Grolmusz, Vince: On some applications of randomized memory., Proceedings of GRACO2005, 203--209, 2005
Csaba István Sidló, András Lukács: Shaping SQL-Based Frequent Pattern Mining Algorithms. In Proc., KDID'05 workshop in conjunction with ECML/PKDD2005, 2005
A. Frieze, R. Martin, J. Moncel, M. Ruszinkó, C. Smyth: Identifying Codes in Random Networks, Proc. of 2005 IEEE International Symposium on Information Theory 4-9 September,Adelaide,Australia,ISBN 0-7803-9151-9/05,pp. 1464-1467, 2005
Grolmusz, V., Király, Z: Generalized Secure Routerless Routing,, , Proceedings of the 4th International Conference on Networking, (ICN) Reunion Island, France, April 17-21, 2005, LNCS No. 3421, pp. 454-462;, 2005
A. Marcus, G. Tardos,: Intersection reverse sequences and geometric applications, Journal of Combinatorial Theory Ser. A 113 (2006) (4),675-691 -552, 2006
ETIK, Eszter Windhager, András A. Benczúr: Eljárás és webkeresoadatbázisok - elonyösen webkeresok adatbázisának - frissítésére (Method, Nemzetközi Szabadalmi Osztályozás: G06F17/30, Ügyszám: P0303101, 2006
Cs. I. Sidló, A. Lukács:: Shaping SQL-Based Frequent Pattern Mining, Springer, LNCS 3933, 188-201., 2006
T. Bohman, A. Frieze, R. Martin, M. Ruszinkó, C. Smyth: On Randomly Generated Intersecting Hypergraphs II,, Random Structures & Algorithms, 2006
A. Gyárfás, M. Ruszinkó, G. Sárközy, E.Szemerédi: An improved bound for the monochromatic cycle partition number, Journal of Combinatorial Theory, Series B,Vol. 96(6) (2006), 855-873., 2006
A. Gyárfás, M. Ruszinkó, G. Sárközy, E. Szemerédi: One-sided coverings of colored complete bipartite graphs,, Algorithms andCombinatorics, Topics in Discrete MathematicsVolume Dedicated to Jarik Nesetril on the Occasion of his 60thBirthday, 2006, ISBN-10 3-540-33698-2, pp. 133-14, 2006
B. Laczay, M. Ruszinkó: Multiple User Tracing Codes, 2006 IEEE International Symposium on Information Theory, July 9-14, Seattle, USA, ISBN 1-4244-0367-7, pp. 1900-1904., 2006
Dudek, Aneta; Katona, Gyula Y.; Wojda, A. Pawe\: Hamiltonian path saturated graphs with small size., Discrete Appl. Math. 154 (2006),no. 9, 1372--1379. 05C45 (05C35), 2006
Frankl, Péter; Katona, Gyula Y: Extremal $k$-edge-Hamiltonian hypergraphs, közlésre elfogadva a Discrete Math.-ban, 2006
A.Hajnal, P.Komjath:: Obligatory subsystems of triple systems, megj. alatt., 2006
I. Benjamini, G. Kozma, L. Lovász, D. Romik, G. Tardos: Waiting fora bat to fly by (in polynomial time),, Combinatorics, Probability and Computing 15 (2006) (5), 673-683., 2006
N. Alon, I. Newman, A. Shen, G. Tardos, N. Vereshagin: Partitioning multidimensional sets in a small number of "uniform" parts,, European J. of Combinatorics 28 (2006) (1), 134-144., 2006
Eszter P. Windhager, Libertad Tansini, Istvan Biro, Devdatt Dubhashi: Iterative Algorithms to Find the Hidden Structure of the Collaborative Filtering Problems,, Winter Meeting of the Department of Computing Science, Chalmers University of Technology, January 2006, Alingsas, Sweden, 2006
Z. Dezső, E. Almaas, A. Lukács, B. Rácz, I. Szakadát, A.-L. Barabási: Fifteen Minutes of Fame: The Dynamics of Information Access on the Web,, Phys. Rev. E 73, 066132 (2006), 2006
T. Szabó, G. Tardos,: Extremal problems for transversals in graphs with bounded degree, Combinatorica 26 (2006) (3), 333-351, Amer. Math. Soc., Providence, RI, 2006
J. Pach, R. Radoicic, G. Tardos, G. Tóth,: Improving the crossing lemma by finding more crossings in sparse graphs,, Discrete and Computational Geometry 36 (2006), 527-552, 2006
G. Simonyi, G. Tardos: Local chromatic Number, Ky Fan's theorem, and circular colorings,, Combinatorica 26 (2006), 587-626. (5), 673-683., 2006
J. Pach, G. Tardos,: Forbidden paths and cycles in ordered graphs and matrices,, Israel Journal of Mathematics 155 (2006), 359-372., 2006
J. Cooper, B. Doerr, J. Spencer, G. Tardos,: Deterministic random walks, Proceedings of the Third Workshop on Analytic Algorithmics and Combinatorics (ANALCO'06), 185-197., 2006
A. Bonato, C. A. Baker, J. M. N. Brown, T. Sz?nyi,: Graphs with the n-e.c. adjacency property constructed from affine planes, közlésre elfogadva a Discrete Math.-nál, 2006
Z. Király, Z. Szigeti:: Simultaneous well-balanced orientations of graphs,, JCT B 96, Issue 5, (2006), pp. 684-692, 2006
A. Frank, Z. Király, B. Kotnyek:: An Algorithm for Node-Capacitated Ring Routing,Operations Research Letters, In Press, Corrected Proof, Available online 24 May 2006, 2006
Z. Király, Z. Szigeti:: Reliable Orientations of Eulerian Graphs,, Egres Tech. Reports, TR-2006-01 (2006)., 2006
A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti:: Recent results on well-balanced orientations,, submitted to Discrete Optimization, 2006
A. Frank, Z. Király, B. Kotnyek:: An Algorithm for Node-Capacitated Ring Routing,, Egres Tech. Reports, TR-2006-04 (2006)., 2006
Grolmusz, Vince, Szabadka Zoltán: Building a Structured PDB: The RS-PDB Database,, Proceedings of the 28th IEEE EMBS Annual International Conference, New York City, Aug. 30-Sept 3, 2006., pp. 5755-5758., 2006
Grolmusz, Vince, Szabadka Zoltán: High Throughput Processing of the Structural Information of the Protein Data Bank, Megjelenés alatt a Journal of Molecular Graphics and Modeling-ben, 2006
Grolmusz, Vince,: Pairs of Codes with Prescribed Hamming Distances and Coincidences, Designs, Codes and Cryptography, Vol 41 (2006) , No. 1., pp. 87-99., 2006
Friedl, Katalin; Ivanyos, Gábor; Santha, Miklos; Verhoeven, Yves F.: Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes., Algorithms and complexity, 380--391, Lecture Notes in Comput. Sci., 3998, Springer, Berlin,, 2006
Friedl, Katalin; Ivanyos, Gábor; Santha, Miklos; Verhoeven, Yves F.: On the black-box complexity of Sperner's lemma., Fundamentals of computation theory, 245--257, Lecture Notes in Comput. Sci., 3623, Springer, Berlin, 2005, 2005
Komjáth, Péter; Totik, Vilmos: Problems and theorems in classical set theory., Problem Books in Mathematics. Springer, New York, 2006. xii+514 pp, 2006
Dzamonja, Mirna; Komjáth, Péter; Morgan, Charles: Wild edge colourings of graphs., J. Symbolic Logic 69 ), no. 1, 255--264., 2004
Blokhuis, A.; Lovász, L.; Storme, L.; Szönyi, T.: On multiple blocking sets in Galois planes., Adv. Geom. 7 (2007), no. 1, 39--53., 2007
Boros, Endre; Szönyi, Tamás; Tichler, Krisztián: On defining sets for projective planes, Discrete Math. 303 (2005), no. 1-3, 17--31., 2005
Gyárfás, András; Ruszinkó, Miklós; Sárközy, Gábor N.; Szemerédi, Endre: Tripartite Ramsey numbers for paths, J. Graph Theory 55 (2007), no. 2, 164--174., 2007
Gyárfás, András; Ruszinkó, Miklós; Sárközy, Gábor N.; Szemerédi, Endre: Three-color Ramsey numbers for paths, Combinatorica 27 (2007), no. 1, 35--69., 2007
Frieze, Alan; Martin, Ryan; Moncel, Julien; Ruszinkó, Miklós; Smyth, Cliff: Codes identifying sets of vertices in random networks, Discrete Math. 307 (2007), no. 9-10, 1094--1107, 2007
Bohman, Tom; Frieze, Alan; Martin, Ryan; Ruszinkó, Miklós; Smyth, Cliff: Randomly generated intersecting hypergraphs. II., Random Structures Algorithms 30 (2007), no. 1-2, 2007
Simonyi, Gábor; Tardos, Gábor: Colorful subgraphs in Kneser-like graphs., European J. Combin. 28 (2007), no. 8, 2007
Cooper, Joshua; Doerr, Benjamin; Spencer, Joel; Tardos, Gábor: Deterministic random walks on the integers, European J. Combin. 28 (2007), no. 8, 2072--2090, 2007
Tardos, Gábor; Tóth, Géza: Multiple coverings of the plane with triangles., Discrete Comput. Geom. 38 (2007), no. 2, 443--450., 2007
Ackerman, Eyal; Tardos, Gábor: On the maximum number of edges in quasi-planar graphs., J. Combin. Theory Ser. A 114 (2007), no. 3, 563--571, 2007
Alon, Noga; Newman, Ilan; Shen, Alexander; Tardos, Gábor; Vereshchagin, Nikolai: Partitioning multi-dimensional sets in a small number of "uniform" parts., European J. Combin. 28 (2007), no. 1, 134--144., 2007
Göring, Frank; Katona, Gyula Y: Local topological toughness and local factors, Graphs Combin. 23 (2007), no. 4, 387--399, 2007
Kano, M.; Katona, G. Y: Structure theorem and algorithm on $(1,f)$-odd subgraph., Discrete Math. 307 (2007), no. 11-12, 2007
Zoltán Szabadka, Rafael Ördög, Vince Grolmusz: The Ramachandran Map of More Than 6,500 Perfect Polypeptide Chains,, Biophysical Reviews and Letters, Vol 2, No. 3 (2007), pp. 1-5, 2007
Zoltán Szabadka, Gábor Iván, Vince Grolmusz:: Being a Binding-Site: Characterizing Residue-Composition of Binding Sites on Proteins, Bioinformation 2(5), 216-221 (2007), 2007
Gábor Iván: An Optimized Distance Function for Comparison of Protein Binding Sites, Lecture Notes in Computer Science Volume 4643/2007, pp. 93-100., 2007
Gábor Iván: Studying Binding Sites of Protein-Ligand Complexes using Data-Mining Algorithms, SEFI and IGIP Joint Annual Conference, Miskolc, Hungary,, 2007
Zoltán Szabadka, Gábor Iván, Vince Grolmusz: Analyzing the Residue-Composition of Metal Binding Sites in the Whole Protein Data Bank, Mol. Biol. Cell 17(suppl), 535, 2006
A. Frieze, R. Martin, J. Moncel, M. Ruszinkó, C. Smyth: Codes identifying sets of vertices in random networks, Discrete Mathematics, 2006
Z. Dezső, E. Almaas, A. Lukács, B. Rácz, I. Szakadát, A.-L. Barabási: Fifteen Minutes of Fame: The Dynamics of Information Access on the Web, Phys. Rev. E 73, 066132, 2006
Rafael Ordog, Zoltán Szabadka, Vince Grolmusz:: Analyzing the Simplicial Decomposition of Spatial Protein Structures, BMC Bioinformatics, 2008, 9(Suppl 1):S11, 2007
Tardos, Gábor; Tóth, Géza: Crossing stars in topological graphs., SIAM J. Discrete Math. 21 (2007), no. 3, 737--749, 2007
M.Csürös and M.Ruszinkó: Single-user tracing and disjointly superimposed codes, IEEE Transactions on Information Theory,Vol.51(4), 2005
P. Komjáth, S, Saharon: Finite Subgraphs of Uncountably Chromatic Graphs, J. Graph Theory 49 (2005) no. 1. 28-38, 2005
Szönyi, Tamás; Cossidente, Antonello; Gács, András; Mengyán, Csaba; Siciliano, Alessandro; Weiner, Zsuzsa: On large minimal blocking sets in ${\rm PG}(2,q)$., J. Combin. Des. 13 (2005), no. 1, 25--41., 2005
Katz, Nets Hawk; Tardos, Gábor: A new entropy inequality for the Erdös distance problem., Towards a theory of geometric graphs, 119--126, Contemp. Math., 342, Amer. Math. Soc., Providence, RI, 2004
Friedl, Katalin; Ivanyos, Gábor; Santha, Miklos: Efficient testing of groups., STOC'05: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 157--166, ACM, New York, 2005
J. Barát, S. Marcugini, F. Pambianco, T. Szőnyi,: Note on Disjoint Blocking Sets in Galois Planes,, J. Combin. Designs 14 (2006), 149-158, 2006



Back »