 |
Ezen az oldalon az NKFI Elektronikus Pályázatkezelő Rendszerében nyilvánosságra hozott projektjeit tekintheti meg.
vissza »
|
 |
Projekt adatai |
|
|
| azonosító |
109240 |
| típus |
K |
| Vezető kutató |
Frank András |
| magyar cím |
Diszkrét optimalizálás és alkalmazásai |
| Angol cím |
Discrete optimization and its applications |
| magyar kulcsszavak |
kombinatorikus optimalizálás, algoritmusok, hálózatok |
| angol kulcsszavak |
combinatorial optimization, algorithms, networks |
| megadott besorolás |
| Matematika (Műszaki és Természettudományok Kollégiuma) | 100 % | | Ortelius tudományág: Diszkrét matematika |
|
| zsűri |
Matematika–Számítástudomány |
| Kutatóhely |
Operációkutatási Tanszék (Eötvös Loránd Tudományegyetem) |
| résztvevők |
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
|
| projekt kezdete |
2013-09-01 |
| projekt vége |
2018-08-31 |
| aktuális összeg (MFt) |
71.256 |
| FTE (kutatóév egyenérték) |
31.28 |
| állapot |
lezárult projekt |
magyar összefoglaló A kutatás összefoglalója, célkitűzései szakemberek számára
Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára.
A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága olyan problémák algoritmikus kezelésére, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Közismert például a legrövidebb út keresésének problémája hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az új, komplex problémák új algoritmusok kifejlesztését igénylik, és ehhez a háttérben húzódó struktúrák megértésére és feltárására van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, amik hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A pályázatban résztvevő kutatók eddig is folytattak kutatásokat az említett irányban és alapvető eredményeket értek el merevségelméletben, játékelméletben és telekommunikációban. Az elméleti vizsgálatokat elősegíti és a gyakorlati kicsatolását biztosítja a kutatócsoport által fejlesztett LEMON programozási csomag.
A kutatás öt fő területre fókuszál: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mindnek fontos alkalmazásai vannak a matematikán kívül: a változós mátrixokat és a merevségelméletet a molekulák szerkezetének vizsgálatánál használják, a stabil párosítások és általánosításaik alapvető eszközök a közgazdaságtanban, a fákkal és hálózati optimalizálással kapcsolatos eredmények pedig a kommunikációs hálózatok tervezésénél. A projekt célja olyan algoritmikus eredmények elérése, melyek komoly hatással lehetnek az említett területekre.
Mi a kutatás alapkérdése?
Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek.
A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága. Ez a terület olyan problémákat közelít meg algoritmikusan, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Ilyenek például legrövidebb út keresése hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az ilyen típusú feladatok megoldásához új algoritmusok kifejlesztésére valamint a háttérben húzódó struktúrák megértésére van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A kutatás az alábbi öt terület főbb nyitott problémáira fog fókuszálni: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mind az öt téma szorosan kapcsolódik a matroidelmélethez és a szubmoduláris optimalizáláshoz, valamint mindnek fontos, matematikán kívüli alkalmazásai is vannak. Az alapvető nyitott kérdések között szerepel például a merevségi mátrixok rangjának kiszámítása, változós mátrixok rangmeghatározásának bonyolultsága valamint közelítő algoritmus keresése a Steiner-fa pakolásokra.
Mi a kutatás jelentősége?
Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának!
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A projekt magában foglalja a kutatócsoport által fejlesztett új szoftverösszetevők fejlesztését is.
A kutatás az alábbi öt területre fog fókuszálni: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mind az öt témának fontos alkalmazásai vannak a matematikán kívül. A változós mátrixok és a merevségelméletet a molekulák szerkezetének vizsgálatánál és hálózati lokalizációs problémák megoldásakor használhatóak. A stabil párosítások és általánosításaik alapvető fogalmakká váltak a közgazdaságtanban (mint azt a legutóbbi közgazdasági Nobel-díj is jelzi). A fákkal, fenyőkkel és hálózati optimalizálással kapcsolatos eredmények központi eszközök vezetékes és vezeték nélküli telekommunikációs hálózatok tervezésénél. A projekt célja az említett témák mögötti matematikai struktúrákba való mélyebb betekintés és ennek alkalmazása olyan algoritmikus eredmények elérésére, melyek lényeges hatással lehetnek ezen területekre.
A kutatás összefoglalója, célkitűzései laikusok számára
Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára.
A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága. Ez a terület olyan problémákat közelít meg algoritmikusan, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Ilyenek például legrövidebb út keresése hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az ilyen típusú feladatok megoldásához új algoritmusok kifejlesztésére valamint a háttérben húzódó struktúrák megértésére van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A pályázatban résztvevő kutatók eddig is folytattak kutatásokat az említett irányban és alapvető eredményeket értek el merevségelméletben, játékelméletben és telekommunikációban. Ezen kezdeményezések támogatása az adott témák diszkrét optimalizálási szemszögből való kutatásán túl elősegíti - a kutatócsoport által fejlesztett LEMON programozási csomag keretében - új szoftverösszetevők fejlesztését is.
A kutatás a diszkrét optimalizálás öt alapvető problémájára fog fókuszálni, melyek közül mindnek van fontos, a korábbiakban már említett, matematikán kívüli alkalmazása is. A projekt célja olyan algoritmikus eredmények elérése, melyek nagy hatással lehetnek ezen területek fejlődésére.
| angol összefoglaló Summary of the research and its aims for experts
Describe the major aims of the research for experts.
Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This sort of expansion into new territories has already started, with members of the project already achieving fundamental results in rigidity theory, game theory and telecommunications.
Amplifying upon this initiative will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have have important applications beyond mathematics: polynomial matrices and rigidity theory are used in the analysis of molecular structures, stable matchings and generalizations are fundamental concepts in economics, while the results on trees and network optimization are basic tools in the design of communication networks. The goal of the project is to obtain algorithmic results that will have significant impact in these areas.
What is the major research question?
Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments.
Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. The research will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have strong ties to matroid theory and submodular optimization, and all of them have important applications beyond mathematics. Fundamental open problems include the characterization of the rank of rigidity matrices, the complexity of computing the rank of polynomial matrices, and approximation algorithms for Steiner tree packing.
What is the significance of the research?
Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have important applications beyond mathematics. Polynomial matrices and rigidity theory are used in the analysis of molecular structures and in network localization problems. Stable matchings and generalizations became fundamental concepts in economics, as exemplified by the latest Nobel prize. The results on trees, arborescences and network optimization are basic tools in the design of communication networks, both wired and wireless. The goal of the project is to obtain new insights into the mathematical structures behind these concepts, and use them in the development of algorithms that will have significant impact in these fields.
Summary and aims of the research for the public
Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others.
Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This sort of expansion into new territories has already started, with members of the project already achieving fundamental results in rigidity theory, game theory and telecommunications.
Amplifying upon this initiative will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas of discrete optimization, which all have important applications beyond mathematics, in the previously mentioned fields. The goal of the project is to obtain algorithmic results that will have significant impact in these areas.
|
|
|
|
|
|
|
|
| |
Közleményjegyzék |
|
|
| 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 |
|
|
|
|
|
|
|
|
|
