Eun Jung Kim (김은정), New algorithm for multiway cut guided by strong min-max duality

Room B232 IBS (기초과학연구원)

Problems such as Vertex Cover and Multiway Cut have been well-studied in parameterized complexity. Cygan et al. 2011 drastically improved the running time of several problems including Multiway Cut and Almost 2SAT by employing LP-guided branching and aiming for FPT algorithms parameterized above LP lower bounds. Since then, LP-guided branching has been studied in depth

Eun Jung Kim (김은정), Twin-width: tractable FO model checking

Room B232 IBS (기초과학연구원)

Inspired by a width invariant defined on permutations by Guillemot and Marx , we introduce the notion of twin-width on graphs and on matrices. Proper minor-closed classes, bounded rank-width graphs, map graphs, Kt-free unit d-dimensional ball graphs, posets with antichains of bounded size, and proper subclasses of dimension-2 posets all have bounded twin-width. On all these classes

Eun Jung Kim (김은정), Solving hard cut problems via flow-augmentation

Room B232 IBS (기초과학연구원)

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) (s,t)-cut of cardinality at most k in an undirected graph G with designated terminals s and t.

Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover

Room B232 IBS (기초과학연구원)

The Weighted F-Vertex Deletion for a class F of graphs asks, given a weighted graph G, for a minimum weight vertex set S such that GSF. The case when F is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal

Eun Jung Kim (김은정), Directed flow-augmentation

Room B332 IBS (기초과학연구원)

We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers s,tV(G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2poly(k) the set Z

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.