Combinatorial optimization: algorithms, structures, applications  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
37547
Type K
Principal investigator Frank, András
Title in Hungarian Kombinatorikus Optimalizálás: Algoritmusok, Strukturák, Alkalmazások
Title in English Combinatorial optimization: algorithms, structures, applications
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Participants Benczúr, András
Fekete, Zsolt
Fige, Péter
Fleiner, Balázs
Fleiner, Tamás
Fülöp, Ottília
Jordán, Tibor
Jüttner, Alpár
Király, Tamás
Király, Zoltán
Kun, Krisztián
Makai, Márton
Maróti, Gábor
Recski, András
Szegő, László
Szigeti, Zoltán
Ujvári, Miklós
Starting date 2002-01-01
Closing date 2006-12-31
Funding (in million HUF) 21.420
FTE (full time equivalent) 0.00
state closed project





 

Final report

  
Results in Hungarian
Mint azt az OTKA-pályázat munkaterve tartalmazza, a pályázatban résztvevő kutatók alkotják a témavezető irányításával működő Egerváry Jenő Kombinatorikus Optimalizálási Kutatócsoportot. A csoport a kutatási tervben szereplő több témában jelentős eredményeket ért el az elmúlt 4 évben, ezekről a pályázat résztvevőinek több mint 50 folyóiratcikke jelent meg, és számos rangos nemzetközi konferencián ismertetésre kerültek. Néhány kiemelendő eredmény: sikerült polinomiális kombinatorikus algoritmust adni irányított gráf pont-összefüggőségének növelésére; jelentős előrelépés történt a háromdimenziós térben merev gráfok jellemzésével és a molekuláris sejtéssel kapcsolatban; 2 dimenzióban sikerült bizonyítani Hendrickson sejtését; a párosításelméletben egy újdonságnak számító módszerrel számos új algoritmikus eredmény született; több, gráfok élösszefüggőségét jellemző tételt sikerült hipergráfokra általánosítani.
Results in English
As the research plan indicates, the researchers participating in the project are the members of the Egerváry Research Group, led by the coordinator. The group has made important progress in the past 4 years in the research topics declared in the research plan. The results have been published in more than 50 journal papers, and have been presented at several prestigious international conferences. The most significant results are the following: a polynomial algorithm has been found for the node-connectivity augmentation problem of directed graphs; considerable progress has been made towards the characterization of 3-dimensional rigid graphs and towards the proof of the molecular conjecture; Hendrickson’s conjecture has been proved in 2 dimensions; several new algorithmic results were obtained in matching theory using a novel approach; several theorems characterizing connectivity properties of graphs have been generalized to hypergraphs.
Full text http://real.mtak.hu/249/
Decision
Yes





 

List of publications

  
Janata M; Loebl M; Szabó J: The Gallai-Edmonds Decomposition for the k-Piece Packing Problem, Electr. J. Combin. (2005) 12 (1) Research Paper 8, 21, 2005
Frank A: On Kuhns Hungarian Method - A tribute from Hungary, NAVAL RESEARCH and LOGISTICS 52: 2-5, 2005
Berg AR; Jordán T: Minimally k-edge-connected directed graphs of maximal size, Graphs and Combinatorics 21: 39-50, 2005
Pap G; Szegő L: Matchings of cycles and paths in directed graphs, Közlésre elfogadva: Combinatorica, 2004
Aharoni R; Fleiner T: On a lemma of Scarf, J Comb Theory B 87: 72-80, 2003
Berg A; Jackson B; Jordán T: Edge splitting and edge-connectivity augmentation in directed hypergraphs, Discrete Math 273: 71-84, 2003
Fleiner T: On the stable b-matching polytope, Mathematical Social Sciences 46: 149-158, 2003
Fekete Z, Jordán T: Uniquely localizable networks with few anchors, Proc. 4th Japanese Hungarian symposium on discrete mathematics and its applications, pp. 144-148, 2005
Fülöp O: Local edge and local node connecrtivity in regular graphs, Studia Sci Math Hungarica 40: 151-158, 2003
Jordán T; Szigeti Z: Detachments preserving local edge-connectivity of graphs, SIAM J Discrete Math 17: 72-87, 2003
Jordán T: Constrained edge-splitting problems, SIAM J Discrete Math 17: 88-102, 2003
Jackson B; Jordán T: Non-separable detachments of graphs, J. Comb Theory B 87: 17-37, 2003
Jüttner A: Optimization with additional variables and constraints, Oper Res Letters 33: 301-311, 2005
Frank A: An algorithm to increase the node-connectivity of a digraph, In: Proc. 3rd Hungarian-Japanese Symposium: 2003. pp. 378-387, 2003
Jordán T; Recski A; Szeszlér D: Rendszeroptimalizálás, Typotex, Budapest, 192 oldal, 2004
Jackson B, Jordán T, Szabadka Z: Globally linked pairs of vertices in equivalent realizations of graphs, Discrete and Computational Geometry, Vol. 35, 493-512, 2006
Makai M: Reroute sequence planning in telecommunication networks and compact vector summation, Appl Math Comput 150: 785-801, 2004
Berg A; Jordán T: Algorithms for graph rigidity and scene analysis, In: Proc. 11th ESA, Springer LNCS 2832: 2003. pp. 78-89, 2003
Cechlárová K; Fleiner T: On a generalization of the stable roommates problem, In: Proc. EUROCOMB’03: 2003. pp. 76-80, 2003
Bárász M; Becker J; Frank A: An algorithm for source location in directed graphs, Oper Res Letters 33: 221-230, 2005
Pap Gy: Hypo-Matchings in Directed Graphs, Proc. Graph Theory 04, Birkhauser, 2006
Spille B; Szegő L: A Gallai-Edmonds type structure theorem for path-matchings, J Graph Theory 46: 93-102, 2004
Frank A: A Magyar Módszer és általánosításai, Szigma 33: 13-44, 2002
Frank A; Shepherd B; Tandon V; Végh Z: Node-capacitated ring routing, Mathematics of Operations Research: 372-383, 2002
Fleiner T: Some results on stable matchings and fixed points, In: Proc. 3rd Hungarian-Japanese Symposium: 2003. pp. 250-261, 2003
Király Z, Szigeti Z: Simultaneous well-balanced orientations of graphs, Journal of Combinatorial Theory, Series B, Volume 96, Issue 5, 684-692, 2006
Jackson B, Jordán T: Connected rigidity matroids and unique realizations of graphs, J. Combinatorial Theory Ser. B., Vol. 94, 1-29, 2005
Király Z; Szabó J: Generalized induced factor problems, In: Proc. 3rd Hungarian-Japanese Symposium: 2003. pp. 103-112, 2003
Pap Gy: Packing non-returning A-paths, Combinatorica, elfogadva, 2005
Sebő A; Szegő L: The Path-packing Structure of Graphs, In: Proc. IPCO X: 2004. pp. 256-270, 2004
Pap G: A TDI description of restricted 2-matching polytopes, In: Proc. IPCO X: 2004. pp. 139-151, 2004
Benczúr A; Végh L: Primal-dual Approach for Directed Vertex Connectivity Augmentation and Generalizations, In: Proc SODA: 2005, 2005
Király T, Pap Gy: Orientations with parity and capacity constraints, Proceedings of 4th Japanese-Hungarian Symposium on Discrete Mathematics, 171-174, 2005
Pap Gy: A combinatorial algorithm to find a maximum even factor, Proc. IPCO XI, 2005
Jackson B; Jordán T: The Dress conjectures on rank in the 3-dimensional rigidity matroid, Advances in Applied Mathematics, Vol. 35, 355-367, 2005
Recski A; Szabó J: On the generalization of the matroid parity problem, Graph Theory 2004, Birkhauser, 2005
Jordán T: A characterization of weakly four-connected graphs, J. Graph Theory, Vol. 52, Issue 3, 217-229, 2006
Király T; Makai M: On polyhedra related to even factors, EGRES Technical Report No. 2003-09, 2003
Cechlárová K; Fleiner T: On a generalization of the stable roommates problem, ACM Transactions on Algorithms, 1(1) 143-156, 2005
Király T; Szabó J: A note on parity-constrained orientations, EGRES Technical Report No. 2003-11, 2003
Janata M; Loebl M; Szabó J: A Gallai-Edmonds type theorem for the k-piece packing problem, EGRES Technical Report No. 2003-12, 2003
Pap G; Szegő L: On factorizations of directed graphs by cycles, EGRES Technical Report No. 2004-01, 2004
Jackson B; Jordán T: Rigid two-dimensional frameworks with three collinear points, Graphs and Combinatorics Vol. 21, No. 4, 427-444, 2005
Berg AR; Jordán T: Two-connected orientations of Eulerian grahps, J. Graph Theory, Vol. 52, Issue 3, 230-242, 2006
Berg AR; Jordán T: Sparse certificates and removable cycles in l-mixed p-connected graphs, Operations Research Letters 33 (2005) 111-114, 2005
Jordán T: On the existence of k edge-disjoint 2-connected spanning subgraphs, J. Combinatorial Theory Ser. B., Vol. 95, 257-262, 2005
Jordán T: On minimally k-edge-connected graphs and shortest k-edge-connected Steiner networks, Discrete Applied Mathematics 131: 421-432, 2003
Király Z, Szigeti Z: Notes on well-balanced orientations, EGRES Technical Report No. 2004-10, 2004
Fekete Zs, Jordán T: Rigid realizations of graphs on small grids, Computational Geometry, Vol. 32, 216-222, 2005
Bernáth A: A note on the directed source location algorithm, EGRES Technical Report No. 2004-12, 2004
Pap Gy: A TDI description of Restricted 2-Matching Polytopes, EGRES Technical Report No. 2004-15, 2004
Iwata S; Király T; Király Z; Szigeti Z: On well-balanced orientations, Proceedings of 4th Japanese-Hungarian Symposium on Discrete Mathematics, 175-182, 2005
Jackson B, Jordán T: On the rank function of the 3-dimensional rigidity matroid, Proc. 4th Japanese Hungarian symposium on discrete mathematics and its applications, pp. 149-153, 2005
Pap Gy: Alternating paths revisited I: even factors, EGRES Technical Report No. 2004-18, 2004
Szabó J: A note on the degree prescribed factor problem, EGRES Technical Report No. 2004-19, 2004
Vaik Zs: On scheduling problems with parallel multi-purpose machines, EGRES Technical Report No. 2005-02, 2005
Fekete Zs; Szabó J: Uniform partitioning to bases in a matroid, EGRES Technical Report No. 2005-03, 2005
Jackson B, Jordán T: Independence free graphs and vertex-connectivity augmentation, J. Combinatorial Theory Ser. B., Vol. 94, 31-77, 2005
Frank A: Restricted t-matchings in bipartite graphs, Discrete Applied Mathematics 131: 337-346, 2003
Király T: Covering symmetric supermodular functions by uniform hypergraphs, J Comb Theory B 91: 185-200, 2004
Pap G; Szegő L: On the maximum even factor in weakly symmetric digraphs, J Comb Theory B 91: 201-213, 2004
Kano M; Katona GY; Király Z: Packing paths of length at least two, Discrete Math 283: 129-135, 2004
Szabó J: Some results on the degree prescribed factor problem, 4th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2005
Berg AR; Jordán T: A proof of Connellys conjecture on 3-connected circuits of the rigidity matroid, J. Comb Theory B 88: 77-97, 2003
Grolmusz V, Király Z: Generalized Secure Routerless Routing, Lecture Notes in Computer Science 3421, Networking - ICN 2005, pp. 454-462, 2005
Fleiner T; Frank A; Iwata S: A costrained independent set problem for matroids, Operations Research Letters 32: 23-26, 2004
Berg A; Jackson B; Jordán T: Highly edge-connected detachments of graphs and digraphs, J Graph Theor 43: 67-77, 2003
Király T, Lau LC: Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs, FOCS 2006, elfogadva, 2006
Jackson B; Jordán T: The d-dimensional rigidity matroid of sparse graphs, J. Combinatorial Theory Ser. B., Vol. 95, 118-133, 2005
Frank A; Szegő L: A note on the path-matching formula, Journal of Graph Theory 41: 110-119, 2002
Frank A; Király Z: Graph orientations with edge-connection and parity constraints, Combinatorica 22: 47-70, 2002
Hartvigsen D; Hell P; Szabó J: The k-piece packing problem, J. Graph Theory (2006) 52, 267--293, 2006
Becker J, Csizmadia Z, Galtier J, Laugier A, Szabó J, Szegő L: An integer programming solution in daisy networks, Networks (2006) 47 116--121., 2006
Makai M: A polyhedral approach to even factors, In: Proc. EUROCOMB03: 2003. pp. 259-263, 2003
Pap G: The H-factor problem in directed graphs, In: Proc. EUROCOMB03: 2003. pp. 298-300, 2003
Szabó J: The generalized Kaneko theorem, In: Proc. 3rd Hungarian-Japanese Symposium: 2003. pp. 92-102, 2003
Pap Gy: Combinatorial algorithms for matchings, even factors, and square-free 2-factors, Mathematical Programming, elfogadva, 2005
Király T; Makai M: On polyhedra related to even factors, In: Proc. IPCO X: 2004. pp. 416-430, 2004
Fekete Z; Jordán T; Whiteley W: An inductive construction for plane Laman graphs via vertex splitting, In: Proc 12th ESA: 2004. pp. 299-310, 2004
Szegő L: On constructive characterizations of (k,l)-sparse graphs, Proc. EUROCOMB03 (Prague, 2003), 342-346, 2003
Frank A: Edge-connection of graphs, digraphs, and hypergraphs, Bolyai Mathematical Society Math. Studies 15, Springer Verlag, 2006, pp. 93-142., 2006
Frank A, Szegő L: Constructive characterizations for packing and covering with trees, Discrete Applied Mathematics 131: 347-371, 2003
Frank A, Király T, Kriesell M: On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Mathematics 131: 373-383, 2003
Frank A, Király T, Király Z: On the orientation of graphs and hypergraphs, Discrete Applied Mathematics 131: 385-400, 2003
Frank A, Király T: Combined connectivity augmentation and orientation problems, Discrete Applied Mathematics 131: 401-419, 2003
Frank A, Király Z, Kotnyek B: An Algorithm for Node-Capacitated Ring Routing, Operations Research Letters, to appear, 2006
Király T, Pap J: Rothblum's description of the stable marriage polyhedron is TDI, 4th Japanese-Hungarian Symposium on Discrete Mathematics, 266-272, 2005



Back »