Office:
-
Department of Operations Research
-
Eötvös Loránd University
-
Pázmány Péter sétány 1/C
-
1117 Budapest
-
Tel: +36-1-372-2500/8582
-
Email address: berkri@cs.elte.hu
-
I am a member of the Egerváry Research Group (EGRES) at the Department of Operations Research. I am writing my PhD thesis under the supervision of András Frank .
Teaching
Informations for students can be found here.
Research
- I am mainly interested in combinatorial optimization, particularly in graph theory. I wrote my master thesis about packings and coverings in directed graphs. The problem of packing subgraphs satisfying given properties is a fundamental question in graph theory that appears in many cases. Edmonds' well-known theorem, for example, gives a characterization of the existence of k disjoint spanning arborescences rooted at the same node.
In 1976, Lovász gave a new proof of this theorem. Since then, his approach became the base of several results about packing arborescences. His proof uses the supermodularity of a special set-funciton, which makes it possible to extend the result to the problem of covering supermodular functions. By combining this idea with the notion of bi-sets introduced by Frank and Jordán, we get a general theorem that also generalizes recent theorems of Kamiyama, Katoh and Takizawa and Fujishige about packing arborescences not necessarily spanning the whole node-set.
- In the last few years I have been working on restricted b-matchings, especially on the case of triangle-free 2-matchings. The problem of finding a maximum 2-matching not containing short cycles can be considered as a relaxation of the Hamiltonian-cycle problem and has been studied intensively. Hartvigsen
and Li proved several results for both subcubic and non-subcubic graphs, but the polyhedral description of the triangle-free 2-matching polytope in general is still open.
Papers
- K. Bérczi and A. Frank, Variations for Lovász' Submodular Ideas ,
In: M. Grötschel and G.O.H. Katona (eds.), Building Bridges: Between Mathematics and Computer Science. Budapest: Springer Verlag - Bolyai Mathematical Society (2008), pp. 137-164. (Bolyai Society mathematical studies; 19.)
- K. Bérczi and A. Frank, Packing Arborescences ,
Technical Report EGRES 2009-04, Department of Operations Research, Eötvös Loránd University, Budapest, May 2009. Also appeared in RIMS Kokyuroku Bessatsu B23: Combinatorial Optimization and Discrete Algorithms ed. S. Iwata, December, 2010
- K. Bérczi, S. Fujishige, N. Kamiyama, A Linear-Time Algorithm to Find a Pair of Arc-disjoint Spanning
In-arborescence and Out-arborescence in a Directed Acyclic Graph ,
Information Processing Letters, Volume 109, Issue 23-24 (2009), pp. 1227-1231.
- K. Bérczi and Y. Kobayashi, An Algorithm for (n-3)-Connectivity Augmentation Problem: Jump System Approach ,
Technical Report METR 2009-12, Department of Mathematical Engineering, University of Tokyo, April 2009. Also appeared in Journal of Combinatorial Theory Series B (2011), doi:10.1016/j.jctb.2011.08.007
- K. Bérczi and L.A. Végh, Restricted b-matchings in Degree-Bounded Graphs ,
In: F. Eisenbrand and F.B. Shepherd (eds.), Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Volume 6080 (2010), pp 43-56.
- K. Bérczi and E.R. Kovács, A note on strongly edge-disjoint arborescences ,
Technical Report EGRES 2011-03, Department of Operations Research, Eötvös Loránd University, Budapest, March 2011.
- K. Bérczi , Subgraphs with restricted degree differences ,
Quick Proof EGRES 2011-04, Department of Operations Research, Eötvös Loránd University, Budapest, May 2011.
- K. Bérczi and E.R. Kovács, Constructive characterization of dumpy digraphs ,
Quick Proof EGRES 2011-05, Department of Operations Research, Eötvös Loránd University, Budapest, May 2011.
- K. Bérczi and E.R. Kovács, A note on conservative costs ,
Quick Proof EGRES 2011-06, Department of Operations Research, Eötvös Loránd University, Budapest, May 2011.
- T. Király, A. Bernáth, L.A. Végh, L. Bajzik, E.R. Kovács, K. Bérczi, A. Jüttner, T. Jordán, Worst case bin packing for OTN electrical layer networks dimensioning ,
13th International Conference on Transparent Optical Networks, June 2011, Stockholm, Sweden
- Zs. Lakatos, L. Bajzik, T. Kárász, K. Bérczi, E.R. Kovács, L.A. Végh, ILP based diverse path routing with node inclusion ,
3rd International Congress on Ultra Modern Telecommunications and Control Systems, October 2011, Budapest, Hungary
- K. Bérczi, The triangle-free 2-matching polytope of subcubic graphs ,
Technical Report EGRES 2012-02, Department of Operations Research, Eötvös Loránd University, Budapest, April 2012.
- K. Bérczi, P. Csikvári, E.R. Kovács, L.A. Végh, Splitting property via shadow systems ,
Technical Report EGRES 2013-02, Department of Operations Research, Eötvös Loránd University, Budapest, March 2013.
Talks
Here are the slides of some recent talks:
Restricted b-matchings , Discrete Convexity and Optimization, Kyoto, October 2012 (invited talk)
The Triangle-free 2-matching Polytope of Subcubic Graphs , The 21st International Symposium on Mathematical Programming, Berlin, August 2012 (invited talk)
A Note on Strongly Edge-Disjoint Arborescences , The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto, June 2011
Restricted b-matchings in Degree-Bounded Graphs , The 14th Conference on Integer Programming and Combinatorial Optimization, Lausanne, June 2010
Packing Arborescences , Kyoto, January 2009
Triathlon
Since 2011, I am a member of the ELTE-BEAC Polythlon Triathlon Club .
-
