Discrete optimization and its applications  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
109240
Type K
Principal investigator Frank, András
Title in Hungarian Diszkrét optimalizálás és alkalmazásai
Title in English Discrete optimization and its applications
Keywords in Hungarian kombinatorikus optimalizálás, algoritmusok, hálózatok
Keywords in English combinatorial optimization, algorithms, networks
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Participants Bérczi, Kristóf
Bernáth, Attila
Fleiner, Tamás
Herskovics, Dávid
Jankó, Zsuzsanna
Jordán, Tibor
Jüttner, Alpár
Kaszanitzky, Viktória Eszter
Király, Csaba
Király, Tamás
Király, Zoltán
Korom, Mátyás
Kovács, Erika Renáta
Pap, Gyula
Starting date 2013-09-01
Closing date 2018-08-31
Funding (in million HUF) 71.256
FTE (full time equivalent) 31.28
state running project





 

Final report

 
Results in Hungarian
A projekt során a pályázat támogatásait is felhasználva 5 PhD értekezés, 6 könyvfejezet és több mint 100 tudományos publikáció született. Olyan nagy presztizsű tudományos folyóiratokban jelentek meg, mint a SIAM J. Disc. Math. (7 db), a J. Comb. Ser. B (2 db), a Math. Op. Res. (3 db), Math. Prog. (2 db) és a Combinatorica (1 db). A fentieken túl a résztvevők számos meghívott és reguláris előadást tartottak olyan tudományos összejöveteleken, mint a bonni Hausdorff intézetben szervezett Komb. Opt. trimeszter keretében tartott workshopok, a BIRS, a CIRM és az ICMS által szervezett workshopok valamint az ISCO, SODA és az Eurocomb konferenciák. A fő eredmények: 1. A vezető kutató és Bérczi a közös háttér feltárásával számos olyan problémára adott jó karakterizációt és polinomiális algoritmust, melyek súlyozott változata már NP-nehéz. 2. Fenyőpakolások témakörében egy új elmélet alakult ki főként a projekt résztvevőinek közreműködésével. Ezzel párhuzamosan fenyőpakolások blokkolása témában is számos eredmény született. 3. A matematika egyéb területeihez is kapcsolódó chip-firing témakörében több algoritmikus és komplexitási eredményt sikerült adni. 4. A network coding témakörén keresztül sikerült egy eddig főként mérnökök által vizsgált területebe matematikai szemlélettel bekapcsolódni. 5. A merevségelmélet számos területén sikerült a komb. opt.-os ismereteket felhasználni összetettebb geomteriai struktúrájú szerkezetek merevségi tulajdonságának vizsgálatára is.
Results in English
Based on the financial support of the project its participants published 5 PhD theses, 6 book chapters and more than 100 other scientific publications. The main results of the project were published in high prestige journals such as SIAM J. Disc. Math. (7), a J. Comb. Ser. B (2), a Math. Op. Res. (3), Math. Prog. (2) és a Combinatorica (1). The members of the group were invited or regular speakers on prestigious scientific meetings such as the workshops organized during the CO trimester program of the Hausdorff Institute, the workshops organized by the BIRS, the CIRM and the ICMSn and conferences like the ISCO, SODA and Eurocomb. The main results: 1. The PI and Bérczi, by exploring the common background, developed characterizations and polynomial algorithms for several problems whose weighted versions are already NP-hard. 2. In the topic of packing arborescences, a new theory arose with a significant impact of the participants of this project. Besides, several results were proved in the topic of blocking arborescence packings. 3. Several algorithmic and complexity results were shown for the chip-firing games which topic is connected to other branches of mathematics. 4. It succeeded to join the researches in network coding - a topic mainly researched by engineers - with a mathematical point of view. 5. The results from CO were used in rigidity theory for the examination of the rigidity properties of frameworks with rather complex geometrical properties too.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=109240
Decision
Yes





 

List of publications

 
Zoltán Király, Neeraja Kulkarni, Ian McMeeking, Joshua Mundinger: The Manickam-Miklós-Singhi Parameter of Graphs and Degree Sequences, arXiv:1808.05835, 2018
Zoltán Király, Dömötör Pálvölgyi: Acyclic orientations with degree constraints, arXiv:1806.03426, 2018
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, and Chao Xu: Beating the 2-approximation factor for Global Bicut, Mathematical Programming, 1-30, 2017
Kristóf Bérczi, AlpárJüttner, Marco Laumanns, Jácint Szabó: Stochastic Route Planning in Public Transport, Transportation Research Procedia 27, 1080-1087, 2017
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Vivek Madan: A tight √ 2-approximation for Linear 3-Cut, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan: Improving the Integrality Gap for Multiway Cut, /arXiv:1807.09735, 2018
Alpár Jüttner, Péter Madarasi: VF2++ - An Improved Subgraph Isomorphism Algorithm, Discrete Applied Mathematics, Vol. 242 pp. 69-81., 2018
Csaba Király, Shin-ichi Tanigawa: Rigidity of Body-Bar-Hinge Frameworks (Chapter 20), in: Handbook of Geometric Constraint Systems Principles (M. Sitharam, A. St. John, J. Sidman eds.). Chapman & Hall, 2018, 2018
Bill Jackson, Tibor Jordán, and Shin-Ichi Tanigawa: Global Rigidity of Two-Dimensional Frameworks (Chapter 21), in: Handbook of Geometric Constraint Systems Principles (M. Sitharam, A. St. John, J. Sidman eds.). Chapman & Hall, 2018, 2018
Tibor Jordán, Water Whiteley: Global Rigidity (Chapter 63), in: Handbook of Discrete and Computational Geometry, (J.E. Goodman, J. O'Rourke, and C. D. Tóth eds.), 3rd edition, CRC Press, Boca Raton, 2017
Csaba Király, Zoltán Szigeti, Shin-ichi Tanigawa: Packing of arborescences with matroid constraints via matroid intersection, EGRES Technical Report no. 2018-08, 2018
Viktória Kaszanitzky, Csaba Király, Bernd Schulze: Sufficient conditions for the global rigidity of periodic graphs, EGRES Technical Report no. 2018-01, 2018
Tibor Jordán: Combinatorial Rigidity: Graphs and Matroids in the Theory of Rigid Frameworks (Chapter II), MSJ Memoirs Vol. 34., 2016
Dóra Erdős, András Frank, Krisztián Kun: Sink-stable sets of digraphs, SIAM J. on Discrete Mathematics, to appear, 2014
Erika R. Kovács, Morten V. Pedersen, Daniel E. Lucani, Frank H. P. Fitzek: Receiver Heterogeneity Helps: Network Coding for Wireless Multi-Layer Multicast, 2014 International Symposium on Network Coding, 2014
Tamás Fleiner , Zsuzsanna Jankó: Choice Function-Based Two-Sided Markets: Stability, Lattice Property, Path Independence and Algorithms, Algorithms 2014, 7(1), 32-59;, 2014
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi: Covering intersecting bi-set famlies under matroid constraints, EGRES Technical Report no. 2013-06; ICGT 2014, 2013
Tamás Király, Júlia Pap: An extension of Lehman's theorem and ideal set functions, ICGT 2014; EGRES Technical Report no. 2013-09, 2013
Tamás Király, Júlia Pap: Complexity of equilibria in linear service-providing games, EGRES Technical Report no. 2012-18 (revised version: March 2014), 2014
Herskovics Dávid: Proof of Berge's path partition conjecture for $k\geq\lambda-3$, ICGT 2014, EGRES Technical Report no. 2013-08, 2013
Tamás Fleiner: On Stable Matchings and Flows, Algorithms, 7(1), 1-14, 2014
Cechlarova Katarina, Fleiner Tamás, Potpinkova Eva:: Assigning evaluators to research grant applications: the case of Slovak Research and Development Agency, SCIENTOMETRICS 99: (2) 495-506, 2014
Attila Bernáth, Gyula Pap: Blocking unions of arborescences, EGRES Technical Report no. 2014-02, 2014
Ildikó Czeller, Gyula Pap: A note on bounded weighted graphic metric TSP, EGRES Technical Report no. 2014-03, 2014
Viktor Kiss, Lilla Tóthmérész: Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph, EGRES Technical Report no. 2014-07, 2014
Zsolt Fekete, Tibor Jordán, Viktória E. Kaszanitzky: Rigid realizations of graphs with two coincident points, Graphs and Combinatorics, online: January, 2014
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Combinatorial conditions for the unique completability of low rank matrices, SIAM J. Discrete Math., to appear. EGRES Technical Report no. 2014-01, 2014
Tibor Jordán, Viktória E. Kaszanitzky: Sparse hypergraphs with applications in combinatorial rigidity, EGRES Technical Report no. 2013-05, 2013
Tibor Jordán, Csaba Király, Shin-ichi Tanigawa: Generic global rigidity of body-hinge frameworks, EGRES Technical Report no. 2014-06, 2014
Viktória Kaszanitzky, Csaba Király: On minimally highly vertex-redundantly rigid graphs, EGRES Technical Report no. 2014-08, 2014
Csaba Király: Augmenting graphs to become (k, l)-redundant, ICGT 2014 -- Booklet of Abstracts, pp. 20, 2014
Csaba Király: On maximal independent arborescence-packing, SIAM Journal on Discrete Mathematics, submitted in 2013, 2015
Attila Bernáth, Zoltán Király: On the tractability of some natural packing, covering and partitioning problems, Discrete Applied Mathematics, in Press, 2014
Tamás Király, Júlia Pap: An extension of Lehman's theorem and ideal set functions, Discrete Applied Mathematics; ICGT 2014; EGRES Technical Report no. 2013-09, 2015
Dávid Herskovics: Proof of Berge's path partition conjecture for $k\geq\lambda-3$, Discrete Applied Mathematics, 2015
Katarina Cechlarova, Tamás Fleiner, Eva Potpinkova:: Assigning evaluators to research grant applications: the case of Slovak Research and Development Agency, SCIENTOMETRICS 99: (2) 495-506, 2014
Attila Bernáth, Gyula Pap: Blocking unions of arborescences, EGRES Technical Report no. 2014-02, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2015), 291-300, 2014
Viktor Kiss, Lilla Tóthmérész: Chip-firing games on Eulerian digraphs and NP-hardness of computing the rank of a divisor on a graph, Discrete Applied Mathematics, 2015
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Combinatorial conditions for the unique completability of low rank matrices, SIAM J. Discrete Math., 2014
Viktória Kaszanitzky, Csaba Király: On minimally highly vertex-redundantly rigid graphs, Graphs and Combinatorics, 2015
Attila Bernáth, Zoltán Király: On the tractability of some natural packing, covering and partitioning problems, Discrete Applied Mathematics 180, 25-36, 2015
Viktória E. Kaszanitzky: Rigidity matroids and inductive constructions of graphs and hypergraphs, ELTE Mat. Doktori Iskola, PhD Thesis, 2015
Csaba Király: Graph structures from combinatorial optimization and rigidity theory, ELTE Mat. Doktori Iskola, PhD Thesis, 2015
Dávid Herskovics: Berge's path partition conjecture: an algorithm for almost all known cases, EGRES Technical Report no. 2015-13, 2015
Erika R. Bérczi-Kovács: Network coding algorithms and applications, ELTE Mat. Doktori Iskola, PhD Thesis, 2015
Bálint Hujter, Viktor Kiss, Lilla Tóthmérész: Reachability of recurrent positions in the chip-firing game, EGRES Technical Report no. 2015-10, 2015
Kristóf Bérczi, Attila Bernáth, Máté Vizer: Regular graphs are antimagic, accepted for publication by the Electronic Journal of Combinatorics, 2015
Kristóf Bérczi, Attila Bernáth, Máté Vizer: A note on v­-free 2­-matchings, EGRES Quick Proof no. 2015-04, 2015
Attila Bernáth, Gyula Pap: Blocking optimal arborescences, EGRES Technical Report no. 2015-06, 2015
Attila Bernáth, Tamás Király: Blocking optimal k-arborescences, EGRES Technical Report no. 2015-09, 2015
Lilla Tóthmérész: Algorithmic aspects of rotor-routing and the notion of linear equivalence, EGRES Technical Report no. 2015-12, 2015
Attila Bernáth, Yusuke Kobayashi, Tatsuya Matsuoka: The generalized terminal backup problem, accepted in SIAM Journal on Discrete Mathematics, 2015
Erika R. Bérczi-Kovács, Attila Bernáth: The complexity of the Clar number problem and an FPT algorithm, arxiv preprint, 2015
Csaba Király: Rigid graphs and an augmentation problem, EGRES Technical Report no. 2015-03, 2015
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi: Algorithmic aspects of covering supermodular functions under matroid constraints, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2015), 301-306, EGRES Technical Report no. 2015-05, 2015
Satoru Fujishige, Tamás Király, Kazuhisa Makino, Kenjiro Takazawa, Shin-ichi Tanigawa: Minimizing submodular functions on diamonds via generalized fractional matroid matchings, EGRES Technical Report no. 2014-14, 2014
Erika R. Bérczi-Kovács: Graph independent field size bounds on failure protecting network codes, EGRES Technical Report no. 2015-01, 2015
Zoltán Király, Erika R. Kovács: Randomized and deterministic algorithms for network coding problems in wireless networks, Information Processing Letters 115:(4) 507-511, 2015
Katarina Cechlarova, Tamás Fleiner, Zsuzsanna Jankó: House-swapping with divorcing and engaged pairs, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015
Alija Pasic, János Tapolcai, Péter Babarczi, Erika R. Bérczi-Kovács, Zoltán Király, L. Rónyai: Survivable Routing Meets Diversity Coding, 14th International IFIP TC6 Networking Conference, Networking 2015, Toulouse, France, May 20-22, 2015
Zoltán Király: Shortest Paths in Nearly Conservative Digraphs, Parameterized and Exact Computation -- IPEC 2014 Wroclaw, LNCS 8894, 234-245., 2014
Zoltán Király: Spanning Tree with Lower Bound on the Degrees, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015
Zoltán Király, Sándor Kisfaludi-Bak: Succinct tree coding for greedy navigation, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi: Covering intersecting bi-set famlies under matroid constraints, SIAM J. Discrete Math. 30-3 (2016), pp. 1758-1774, 2016
Tamás Király, Júlia Pap: An extension of Lehman's theorem and ideal set functions, Discrete Applied Mathematics 209 (2016), 251-263, 2016
Dávid Herskovics: Proof of Berge's path partition conjecture for $k\geq\lambda-3$, Discrete Applied Mathematics, Volume 209, 20 August 2016, Pages 137-143., 2016
Tibor Jordán, Csaba Király, Shin-ichi Tanigawa: Generic global rigidity of body-hinge frameworks, Journal of Combinatorial Theory, Series B Volume 117, March 2016, Pages 59–76, 2016
Viktória E. Kaszanitzky, Csaba Király: On minimally highly vertex-redundantly rigid graphs, Graphs and Combinatorics ) 32:225-240, 2015
Kristóf Bérczi, Attila Bernáth, Máté Vizer: Regular graphs are antimagic, The Electronic Journal of Combinatorics 22 (3), (2015) P3. 34, 2015
Attila Bernáth, Gyula Pap: Blocking optimal arborescences, Math. Program. (2016). doi:10.1007/s10107-016-1025-3, 2016
Attila Bernáth, Tamás Király: Blocking optimal k-arborescences, Proceeding SODA '16 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms Pages 1682-1694, 2016
Katarina Cechlarova, Tamás Fleiner, Zsuzsanna Jankó: House-swapping with divorcing and engaged pairs, Discrete Applied Mathematics, 206, 19, pp 1-8, 2016
Tamás Király: Base polyhedra and the linking property, EGRES Technical Report no. 2016-06., 2016
Kristóf Bérczi: A note on packing half-regular bipartite graphs, EGRES Quick Proofs QP-2016-01, 2016
Kristóf Bérczi, Attila Joó: King-serf duo by monochromatic paths in k-edge-coloured tournaments, EGRES Technical Reports TR-2016-08, 2016
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization I: Branchings and matchings, EGRES Technical Reports TR-2016-09, 2016
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation, EGRES Technical Reports TR-2016-10, 2016
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization III: Highly connected digraphs, EGRES Technical Reports TR-2016-09, 2016
Kristóf Bérczi, Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, EGRES Technical Reports TR-2016-12, 2016
Kristóf Bérczi, Yusuke Kobayashi: The directed disjoint shortest paths problem, EGRES Technical Reports TR-2016-13, 2016
Bill Jackson, Viktória Kaszanitzky, Anthony Nixon: Rigid cylindrical frameworks with two coincident points, EGRES Technical Report no. 2016-05, 2016
Viktória Kaszanitzky, Bernd Schulze: Characterizing minimally flat symmetric hypergraphs, EGRES Technical Report no. 2015-17, 2015
Tamás Fleiner, Gábor Wiener: Coloring signed graphs using DFS, OPTIMIZATION LETTERS, 2016
András Frank, Tibor Jordán: Graph connectivity augmentation, In: K. Thulasiraman, S. Arumugam, A. Brandstadt, T. Nishizeki (eds.), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, pp. 313-346 (Chapter 14), 2015
Bálint Hujter, Viktor Kiss, Lilla Tóthmérész: On the complexity of the chip-firing reachability problem, EGRES Technical Report no. 2015-10, 2015
Bálint Hujter, Lilla Tóthmérész: Chip-firing based methods in the Riemann-Roch theory of directed graphs, EGRES Technical Report no. 2016-01, 2016
Zoltán Király, Lilla Tóthmérész: On some special cases of Ryser's conjecture, EGRES Technical Report no. 2016-14, 2016
Viktória E. Kaszanitzky, Bernd Schulze: Lifting symmetric pictures to polyhedral scenes, EGRES Technical Report no. 2015-07, 2015
János Tapolcai, Gábor Rétvári, Péter Babarczi, Erika R. Bérczi-Kovács, Panna Kristóf, Gábor Enyedi: Scalable and efficient multipath routing: Complexity and algorithms, 23rd IEEE International Conference on Network Protocols, ICNP 2015. San Francisco, USA Piscataway: IEEE Computer Society, 2016. pp. 376-385., 2016
Erika R. Bérczi-Kovács, Attila Bernáth: On the Clar number of benzenoid hydrocarbons, arXiv, 2016
Sergey I. Nikolenko, Kirill Kogan , Gábor Rétvári, Erika R. Bérczi-Kovács, Alexander Shalimov: How to Represent IPv6 Forwarding Tables on IPv4 or MPLS Dataplanes, In: 19th IEEE Global Internet Symposium (IEEE GI 2016). San Francisco, USA, pp. 1-6., 2016
Kristóf Bérczi, Alpár Jüttner: Road surveillance optimization—an asymmetric vehicle routing problem with visiting frequencies, In The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, jun 2015., 2015
Alpár Jüttner, Kristóf Bérczi: Arrival Time Dependent Routing Policies in Public Transport, ECCO XXIX, 29th Conference of the European Chapter on Combinatorial Optimization (ECCO), May 26 - 28, 2016, Budapest, Hungary, 2016
Péter Madarasi, Alpár Jüttner: Improved Algorithms for Matching Biological Graphs, ECCO XXIX, 29th Conference of the European Chapter on Combinatorial Optimization (ECCO), May 26 - 28, 2016, Budapest, Hungary, 2016
Péter Györgyi, Bálint Hujter, Sándor Kisfaludi-Bak: On the number of touching pairs in a set of planar curves, arXiv, 2015
András Gyárfás, Zoltán Király: Covering complete partite hypergraphs by monochromatic components, EGRES Technical Report no. 2016-03, 2016
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Unique Low Rank Completability of Partially Filled Matrices, Journal of Combinatorial Theory, Series B Volume 121, Pages 432–462 (Special Issue: Fifty years of The Journal of Combinatorial Theory.), 2016
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi: Covering intersecting bi-set famlies under matroid constraints, SIAM J. Discrete Math. 30-3 (2016), pp. 1758-1774, 2016
Csaba Király: On maximal independent arborescence packing, SIAM Journal on Discrete Mathematics 30(4), 2107–2114, 2016
Bálint Hujter, Viktor Kiss, Lilla Tóthmérész: Reachability of recurrent positions in the chip-firing game, Proceedings of the American Mathematical Society, 145, 3343-3356, 2017
Tamás Király: Base polyhedra and the linking property, Journal of Combinatorial Optimization, 2017
Kristóf Bérczi, Attila Joó: King-serf duo by monochromatic paths in k-edge-coloured tournaments, ELectronic Journal of Combinatorics, Volume 24, Issue 1, Paper #P1.42, 2017
Kristóf Bérczi, Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, Discrete Applied Mathematics, 226 (C), 10-16, 2017
Tamás Fleiner, Gábor Wiener: Coloring signed graphs using DFS, OPTIMIZATION LETTERS Volume 10, Issue 4, pp 865-869, 2016
Bálint Hujter, Viktor Kiss, Lilla Tóthmérész: On the complexity of the chip-firing reachability problem, Proceedings of the American Mathematical Society 145, 3343-3356, 2017
Viktória E. Kaszanitzky, Bernd Schulze: Lifting symmetric pictures to polyhedral scenes, ARS MATHEMATICA CONTEMPORANEA 13:(1) pp. 31-47., 2017
András Gyárfás, Zoltán Király: Covering complete partite hypergraphs by monochromatic components, Discrete Mathematics, 340 pp. 2753-2761., 2017
András Gyárfás, Zoltán Király, Lilla Tóthmérész:: On Ryser's Conjecture, 10th Japanese-Hungarian Symposium, 2017, Budapest, 2017
Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi: Making bipartite graphs DM-irreducible, arXiv, 2016
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu: Global and fixed-terminal cuts in digraphs, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) Klaus Jansen and José D. P. Rolim and David Williamson and Sa, 2017
Kristóf Bérczi, Erika R. Bérczi-Kovács: Directed hypergraphs and Horn minimization, Information Processing Letters, 128, 32-37, 2017
Kristóf Bérczi, Zoltán Király, István Miklós: Packing tree degree sequences, arXiv, 2017
Tamás Fleiner, Zsuzsanna Jankó: On Weighted Kernels of Two Posets, ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 33:(1) pp. 51-65., 2016
Tamás Fleiner, Zsuzsanna Jankó, Akihisa Tamura, Alexander Teytelboym: Trading Networks with Bilateral Contracts, arXiv, 2015
Jankó Zsuzsanna: Structure of generalized stable matchings, ELTE Mat. Doktori Iskola, PhD Thesis, 2017
Tóthmérész Lilla: The chip-firing game, ELTE Mat. Doktori Iskola, PhD Thesis, 2017
Király Tamás, Mészáros-Karkus Zsuzsa: Finding strongly popular b-matchings in bipartite graphs, Electronic Notes in Discrete Mathematics, Volume 61, Pages 735-741, 2017
Erika R. Bérczi-Kovács, Attila Bernáth: The complexity of the Clar number problem and an exact algorithm, EGRES Technical Report no. 2016-20, 2016
Péter Babarczi, János Tapolcai, Alija Pašić, Lajos Rónyai, Erika R. Bérczi-Kovács, Muriel Médard: Diversity Coding in Two-Connected Networks, IEEE/ACM Transactions on Networking, 2017
Kristóf Bérczi, Attila Bernáth, Tamás Király, Gyula Pap: Blocking optimal structures, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications May 22-25, 2017, Budapest, Hungary. 67-76, 2017
Attila Bernáth: Covering symmetric supermodular functions with graph edges: A short proof of a theorem of Benczúr and Frank, Information Processing Letters Volume 128, Pages 49-53, 2017
Csaba Király, Zoltán Szigeti: Reachability-based matroid-restricted packing of arborescences, 10th Japanese-Hungarian Symposium, 2017, 2017
Quentin Fortier, Csaba Király, Marion Léonard, Zoltán Szigeti, Alexandre Talon: Old and new results on packing arborescences, EGRES Technical Report no. 2016-04, 2016
Quentin Fortier, Csaba Király, Zoltán Szigeti, Shin-ichi Tanigawa: On packing spanning arborescences with matroid constraint, Electronic Notes in Discrete Mathematics Volume 61, Pages 451-457, 2017
Viktória E. Kaszanitzky, Bernd Schulze: Sufficient connectivity conditions for rigidity of symmetric frameworks, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017
Tibor Jordán: Extremal problems and results in combinatorial rigidity, 10th Japanese-Hungarian Symposium, 2017
Tibor Jordán, Shin-ichi Tanigawa: Global rigidity of triangulations with braces, 10th Japanese-Hungarian Symposium, 2017
Gyula Pap: Some observations on the traveling salesman problem, 10th Japanese-Hungarian Symposium, 2017, 2017
Viktória Kaszanitzky, Bernd Schulze, Shin-ichi Tanigawa: Global Rigidity of Periodic Graphs under Fixed-lattice Representations, EGRES Technical Report no. 2016-21, 2016
Bálint Hujter: The chip-firing halting problem for multigraphs and convex cost flows, EGRES Technical Report no. 2017-01, 2017
Alpár Jüttner, Péter Madarasi: A Primal-Dual Approach for Large Scale Integer Problems, 10th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Budapest, 2017
Tibor Jordán, Viktória E. Kaszanitzky: Sparse hypergraphs with applications in combinatorial rigidity, Discrete Applied Mathematics, 2015
Kristóf Bérczi, Attila Bernáth, Máté Vizer: Regular graphs are antimagic, The Electronic Journal of Combinatorics 22 (3), (2015) P3. 34, 2015
Lilla Tóthmérész: Algorithmic aspects of rotor-routing and the notion of linear equivalence, Discrete Applied Mathematics, 2018
Erika R. Bérczi-Kovács, Attila Bernáth: The complexity of the Clar number problem and an exact algorithm, Journal of Mathematical Chemistry, 2017
Zoltán Király: Spanning Tree with Lower Bound on the Degrees, Discrete Applied Mathematics, 242, pp. 82-88, 2018
Kristóf Bérczi, Attila Joó: King-serf duo by monochromatic paths in k-edge-coloured tournaments, ELectronic Journal of Combinatorics, Volume 24, Issue 1, Paper #P1.42, 2017
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization I: Branchings and matchings, Mathematics of Operations Research, Vol. 43, Iss. 3, 726–753., 2018
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation, Mathematics of Operations Research, Vol. 43, Iss. 3, 754–762., 2018
Kristóf Bérczi, András Frank: Supermodularity in unweighted graph optimization III: Highly connected digraphs, Mathematics of Operations Research, Vol. 43, Iss. 3 763–780., 2018
Kristóf Bérczi, Yusuke Kobayashi: The directed disjoint shortest paths problem, LIPIcs-Leibniz International Proceedings in Informatics 87, 2017
Viktória Kaszanitzky, Bernd Schulze: Characterizing minimally flat symmetric hypergraphs, Discrete Applied Mathematics, 2018
Alpár Jüttner, Kristóf Bérczi, Marco Laumanns, Jácint Szabó: Arrival Time Dependent Routing Policies in Public Transport, Discrete Applied Mathematics, 2018
Péter Györgyi, Bálint Hujter, Sándor Kisfaludi-Bak: On the number of touching pairs in a set of planar curves, COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 67. pp. 29-37, 2017
Kristóf Bérczi, Satoru Iwata, Jun Kato, Yutaro Yamaguchi: Making bipartite graphs DM-irreducible, SIAM Journal on Discrete Mathematics 32 (1), 560-590, 2018
Kristóf Bérczi, Attila Bernáth, Tamás Király, Gyula Pap: Blocking optimal structures, Discrete Mathematics 341(7): 1864-1872, 2018
Quentin Fortier, Csaba Király, Marion Léonard, Zoltán Szigeti, Alexandre Talon: Old and new results on packing arborescences, Discrete Applied Mathematics (242), 2018
Viktória E. Kaszanitzky, Bernd Schulze: Sufficient connectivity conditions for rigidity of symmetric frameworks, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017
Zoltán Király, Lilla Tóthmérész: On Ryser's Conjecture for $t$-Intersecting and Degree-Bounded Hypergraphs, Electronic Journal of Combinatorics, 24(4), art. no. #P4.40, 2017
Erika R Bérczi‐Kovács, Zoltán Király: Optimal and Heuristic Network Coding Algorithms for Multi-Layered Video Broadcast, Networks, 2018
Andreas Gross, Farbod Shokrieh, Lilla Tóthmérész: Effective divisor classes on metric graphs, EGRES Technical Report no. 2018-16, 2018
András Mészáros: A note on disjoint dijoins, Combinatorica, 2018
Zsuzsa Mészáros-Karkus: Hardness results for stable exchange problems, Theoretical Computer Science, 2017
László Varga: Combinatorial Nullstellensatz Modulo Prime Powers and the Parity Argument, The Electronic Journal of Combinatorics, 2014
Pap Gyula, Varnyú József: Synchronized Traveling Salesman Problem, EGRES Technical Report no. 2018-15, 2018
András Frank, Kazuo Murota: Discrete Decreasing Minimization, Part I, Base-polyhedra with Applications in Network Optimization, arXiv:1808.07600v1 [math.CO] 23, August 2018 (52 pages)., 2018
András Frank, Kazuo Murota: Discrete Decreasing Minimization, Part II, Views from discrete convex analysis, arXiv:1808.08477v1 [math.CO] 25 Aug 2018 (43 pages), 2018
Attila Bernáth, Roland Grappe, and Zoltán Szigeti: Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph, SIAM J. Discrete Math., 31(1), 335–382., 2017





 

Events of the project

 
2015-06-17 19:27:55
Résztvevők változása




Back »