Loading Events

« All Events

  • This event has passed.
:

Fedor Fomin, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms

March 10 Thursday @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

We examine algorithmic extensions of two classic results of extremal combinatorics. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a 2-connected graph G with the average vertex degree D>1, contains a cycle of length at least D.

We discuss the recent progress in parameterized complexity of computing long cycles “above” the guarantees established by these classical theorems: cycles of lengths at least 2d+k and D+k.

The talk is based on the joint works with Petr Golovach, Danil Sagunov, and Kirill Simonov.

Details

Date:
March 10 Thursday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.