The area of Algorithmic Graph Theory is part of the interface between combinatorial mathematics and computer science. It deals with the design and analysis of algorithms to solve graph theory problems, such as maximum independent set  and related problems (maximum clique, maximum matching), graph coloring, domination in graphs, routing problems (shortest path, Hamiltonian cycle, travelling salesman, and minimum weight k-connected spanning subgraphs), etc.

 

Sample publications:

• C.T. Hoang, M. Kaminski, V.V. Lozin, J. Sawada, and X. Shu. Deciding k-colorability of P₅-free graphs in polynomial time.  Algorithmica, 57(1): 74 - 81, 2010.
• V.V. Lozin, and M. Milanic. A Polynomial Algorithm to Find an Independent Set of Maximum Weight in a Fork-free Graph. Journal of Discrete Algorithms, 6(4): 595 - 604, 2008.
• H. Räcke. Optimal Hierarchical Decompositions for Congestion Minimization in Networks. Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC'08), pages 255 - 264, 2008. Co-Winner of the STOC'2008 Best Paper Award.
• V.V. Lozin,and M. Milanic. On Finding Augmenting Graphs. Discrete Applied Mathematics, 156(13): 2517 - 2529, 2008.
• A. Czumaj and A. Lingas. Approximation Schemes for Minimum-cost k-Connectivity Problems in Geometric Graphs. Chapter 51 in Handbook of Approximation Algorithms and Metaheuristics, edited by T.F. Gonzalez, CRC Press, Boca Raton, FL, 2007.
• D. Cardoso, M. Kaminski and V.V. Lozin. Maximum k-regular Induced Subgraphs. Journal of Combinatorial Optimization, 14: 455 - 463, 2007.
• A. Czumaj and A. Lingas. Finding a Heaviest Triangle is not Harder than Matrix Multiplication. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA'07), pages 986 - 994, 2007.
• V. Deineko, G.J. Woeginger, and Klinz. Exact Algorithms for the Hamiltonian Cycle Problem in Planar Graphs. Operations Research Letters, 34: 269 - 274, 2006.
• M.T. Hajiaghayi and H. Räcke. An O(n^1/2)-Approximation Algorithm for Directed Sparsest Cut. Information Processing Letters, 97(4): 156 - 160, February 2006.
• A. Berger, A. Czumaj, M. Grigni, and H. Zhao. Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA'05), pages 472 - 483, 2005.
• V.E. Alekseev, D.V. Korobitsyn and V.V. Lozin. Boundary Classes of Graphs for the Dominating Set Problem. Discrete Mathematics, 285: 1 - 6, 2004.
• A. Czumaj and C. Sohler. Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-time. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC'04), pages 175 - 183, 2004.
• A. Czumaj, M. Grigni, P. Sissokho, and H. Zhao. Approximation Schemes for Minimum 2-edge-connected and Biconnected Subgraphs in Planar Graphs. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04), pages 489 - 498, 2004.
• M.U. Gerber and V.V. Lozin. Robust Algorithms for the Stable Set Problem. Graphs and Combinatorics, 19: 347 - 356, 2003.
• M. Kochol, V.V. Lozin, and B. Randerath. The 3-colorability Problem on Graphs with Maximum Degree Four. SIAM J. Computing, 32: 1128 - 1139, 2003.
• H. Räcke. Minimizing Congestion in General Networks. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), pages 43 - 52, 2002. Winner of the FOCS'2002 Best Paper Award.
• V.V. Lozin. On Maximum Induced Matchings in Bipartite Graphs. Information Processing Letters, 81(1): 7 - 11, 2002.
• A. Czumaj and A. Lingas. On Approximability of the Minimum-Cost k-Connected Spanning Subgraph Problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'99), pages 281 - 290, 1999.