Combinatorial optimization: algorithms, structures, applications (a supplementary to the running OTKA-project with the same title no. T 037547)  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
49788
Type NI
Principal investigator Frank, András
Title in Hungarian Kombinatorikus optimalizálás: Algoritmusok, Struktúrák, Alkalmazások
Title in English Combinatorial optimization: algorithms, structures, applications (a supplementary to the running OTKA-project with the same title no. T 037547)
Panel Natural Sciences large proposals
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Participants Bárász, Mihály
Bernáth, Attila
Fekete, Zsolt
Makai, Márton
Pap, Gyula
Szabó, Jácint
Starting date 2005-01-01
Closing date 2008-08-31
Funding (in million HUF) 19.140
FTE (full time equivalent) 20.88
state closed project





 

Final report

  
Results in Hungarian
Az ELTE Operációkutatási tanszékén folyó kombinatorikus optimalizálási kutatások keretét több egymással párhuzamosan futó pályázat és egyéb kutatástámogatási szerződés határozza meg. Mindezek alapja egyrészt az MTA-ELTE Egerváry Jenő Kutatócsoport (EGRES), amelynek keretében három fiatal kutató foglalkoztatására van lehetőség, valamint az ELTE TTK matematika doktori iskolája: átlagban 5-6 ösztöndíjas doktorandusz hallgató dolgozik nálunk kombinatorikus optimalizálási területen. Az elméleti vizsgálatok gyakorlati kicsatolását támogatja a France Telecommal kötött kutatási szerződés, az ETIK (Egyetemközi Távközlési és Informatikai központ) és a Siemens. 2004 és 2007 között egy európai Marie Curie pályázat (ADONET) résztvevőiként jelentős támogatást kaptunk fiatal kutatóink külföldi látogatásainak elősegítésére és számos külfüldi kutató dolgozott nálunk hosszabb-rövidebb ideig. Működésünk alapvető támasza egy jövőre befejeződő kutatási OTKA pályázat. Ebbe a háttérbe illeszkedett az OTKA TS049788 kódszámú Tudományos Iskola pályázata, amely pótolhatatlan szerepet játszott a csoportunk eredményes működésében. Ifjú kutatóink munkáikat rangos konferenciákon mutathatták be és tekintélyes szaklapokban publikálták. Több, mint 30 olyan publikáció keletkezett, amely szorosan köthető az OTKA pályázathoz. Jelentős siker, hogy mind Pap, mind Szabó kutatási eredményeiért elnyerte a Bolyai Társulat Grünwald Géza emlékdíját, míg Pap Gyula megkapta az MTA Ifjúsági Díját is!
Results in English
The frame of research in combinatorial optimization at the Operations Research Department of the ELTE University is determined by several projects and research funding contracts running parallel. The basis is the MTA-ELTE Egerváry Jenő Research Group (EGRES), that allows us to employ 3 young researchers. Moreover in the mathematics doctoral school of ELTE we have 5-6 PhD students working in combinatorial optimization on average. The practical applications of theoretical research is funded by a contract with France Telecom, by ETIK (Inter-University Cooperative Research Centre) and by Siemens. As the participants of an European Marie Curie network (ADONET) between 2004 and 2007 we received a significant contribution for our young researchers to visit colleagues abroad and we had many foreign researchers visiting us, too. The main support of our functioning is an OTKA project that will end next year. The current OTKA Scientific School project of code TS049788 fit this background and it played an important role in the successful functioning of our group. Our young researchers could present their work at highly ranked international conferences, and they published their results at prestigious journals. More than 30 publications were born directly in this project. It is an important success that both Pap and Szabó obtained the Grünwald Géza Prize from the Bolyai Mathematical Society, moreover Gyula Pap also obtained the Juvenile Prize of the Hungarian Academy of Sciences.
Full text http://real.mtak.hu/2027/
Decision
Yes





 

List of publications

  
Pap Gy: Alternating paths revisited II: restricted b-matchings in bipartite graphs, EGRES Tecnical Report TR-2005-13, http://www.cs.elte.hu/egres, 2005
Pap Gy: A constructive approach to matching and its applications, PhD disszertáció, 2007
Pap Gy: Alternating paths revisited III: hypo-matchings in directed graphs, EGRES Tecnical Report TR-2005-14, http://www.cs.elte.hu/egres, 2005
Makai M; Pap Gy; Szabó J: Matching problems in polymatroids without double circuits, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, volume 4513 of Lecture Notes in Computer Science. Springer, 2007
Pap Gy: Hypo-matchings in directed graphs, Graph Theory in Paris. Proceedings of a Conference in Memory of Claude Berge, Trends in Mathematics, pages 325-335. Birkhäuser, 2007
Pap Gy: Packing non-returning a-paths, Combinatorica, 27(2):247-251, 2007
Fekete Zs: Source location with rigidity and tree packing requirements, Operations Research Letters 34(6): 607-612, 2006
Pap Gy: Combinatorial algorithms for matchings, even factors and square-free 2-factors, Math. Program., 110(1):57-69, 2007
Pap Gy: Packing non-returning a-paths algorithmically, Discrete Mathematics, 308(8):1472-1488, 2008
Fekete Zs; Jordán T: Uniquely localizable networks with few anchors, ALGOSENSORS 2006, Lecture Notes in Computer Science 4240: 176-183, 2006
Fekete Zs; Szegő L: A note on [k,l]-sparse graphs, Proceedings of Graph Theory 2004, a conference in memory of Claude Berge, Paris, 2006
Bernáth A; Gerbner D: Chain intersecting families, Graphs Combin., 23(4):353-366, 2007
Bernáth A: Metsző halmazrendszerek reprezentálása [A representation for intersecting families], Mat. Lapok (N.S.), 13(1):6-12, 2006/07, 2006
Bernáth A: Hardness results for well-balanced orientations, Technical Report TR-2006-05, Egerváry Research Group, Budapest, 2006. www.cs.elte.hu/egres, 2006
Bernáth A; Joret G: Well-balanced orientations of mixed graphs, Inf. Process. Lett., 106(4):149-151, 2008
Bernáth A; Király T: A new approach to splitting-off, Proceedings of the 13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008, volume 5035 of Lecture Notes in Computer Science, page, 2008
Bernáth A; Iwata S; Király T; Király Z; Szigeti Z: Recent results on well-balanced orientations, Discrete Optimization, 5(4):663-676, 2008
Bernáth A: Source location in undirected and directed hypergraphs, Oper. Res. Lett., 36(3):355-360, 2008
Bernáth A; Király T: Covering symmetric skew-supermodular functions with hyperedges, Technical Report TR-2008-05, Egerváry Research Group, Budapest, 2008
Bernáth A: Egy extremális halmazelméleti probléma [On a problem in extremal set theory], Mat. Lapok (N.S.), 10(2):2-4, 2005
Kovács E; Végh L: The constructive characterization of $(k,\ell)$-edge-connected digraphs, Technical Report TR-2008-14, Egerváry Research Group, www.cs.elte.hu/egres, 2008
Harks T; Végh L: Nonadaptive selfish routing with online demands, Combinatorial and Algorithmic Aspects of Networking (2007), pp. 27-45., 2007
Szabó J: Graph packings and the degree prescribed subgraph problem, PhD disszertáció, 2006
Frank A; Lau Chi L; Szabó J: A note on degree-constrained subgraphs, Discrete Mathematics, 308(12):2647-2648, 2008
Szabó J: Éldiszjunkt útrendszer kiterjesztése [Extending an edge-disjoint path-system], Alk. Mat. Lapok, 25:119-129, 2008
Hartvigsen D; Hell P; Szabó J: The k-piece packing problem, J. Graph Theory, 52(4):267-293, 2006
Makai M; Szabó J: The parity problem of polymatroids without double circuits, Combinatorica, 2008. megjelenés alatt, 2008
Szabó J: Good characterizations for some degree constrained subgraphs, J. Combinatorial Theory, Ser B, 2008. megjelenés alatt, 2008
Szabó J: Packing trees with constraints on the leaf degree, Graphs and Combin., 2008. (megjelenés alatt), 2008
Szabó J: Matroid Parity and Jump Systems: A Solution to a Conjecture of Recski, SIAM Journal on Discrete Mathematics, 22:854, 2008
Makai M: Rigid graphs from edge-pairs, 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pages 199-208, June 2005, 2005
Makai M: Matroid matching with Dilworth truncation, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), volume AE of DMTCS Proceedings, pages 175-180., 2005
Bárász M; Fekete Zs; Jüttner A; Makai M; Szabó J: Qos aware and fair resource allocation scheme in transport networks, 8th International Conference on Transparent Optical Networks (ICTON), Nottingham, United Kingdom, June 2006, 2006



Back »