기초과학연구원 이산수학그룹
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, …
Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of …
Given a minor-closed graph class ${\cal G}$, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$, we define …
Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, …
An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology, Roberts defined the boxicity of a graph G to …
The local connectivity $ \kappa_D(r,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $r\rightarrow v $ paths in $ …
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries …
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until …
Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced …
The Alon-Jaeger-Tarsi conjecture states that for any finite field $\mathbb{F}$ of size at least 4 and any nonsingular matrix $M$ over $\mathbb{F}$ there exists a vector $x$ such that neither …