Noleen Köhler, Testing first-order definable properties on bounded degree graphs

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

Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study

Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins

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

We introduce the notion of delineation. A graph class $\mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $\mathcal D$ of a subclass of $\mathcal C$, it holds that $\mathcal D$ has bounded twin-width if and only if $\mathcal D$ is monadically dependent. An effective strengthening of delineation for

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:, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.