报告题目：Feedback Arc Set Bounds for Digraphs of Bounded Maximum Degree
报告人： Gutin
报告时间： 1月12日 10:00-11:00
报告地点： 四教219
报告摘要： We studied upper bounds for the minimum size (weight) of feedback arc set in unweighted (arc-weighted) digraphs. In particular, we used our bounds to prove a conjecture and disprove another one. We also studied bounds for the maximum number of feedback arc sets partitioning a digraph with lower -bounded directed girth, the parameter already introduced by Douglas R. Woodal in 1976.
报告人简介：Gregory Gutin. He studied for PhD under Professor Noga Alon at the School of Mathematics, Tel Aviv University, Israel and received his PhD (with distinction) in 1993. In 1996 he was awarded Kirkman Medal of International Institute of Combinatorics and Applications. Since 1st September 2000, Gregory has been Professor of Computer Science, Department of Computer Science, Royal Holloway, University of London. He held Royal Society Wolfson Research Merit award in 2014-2018 and was elected to Academia Europaea in 2017 and to AAIA (Asia-Pacific Artificial Intelligence Association) in 2021. He received best paper awards at information security access control symposium ACM SACMAT in 2015, 2016, 2021 and 2022. In 2019 he was presented with Amity Global Academic Excellence Award and in 2022 with AAIA Outstanding Contribution Award.
Gutin's main research interests include graphs and combinatorics, parameterized, polynomial, exact and approximation algorithms and combinatorial optimizationG. Gutin published two editions of a monograph (translated into Chinese) and edited two books. He has more than 250 papers published or accepted for publication in refereed journals and conference proceedings. His publications were cited over 11900 times.