Tomáš Masařík, Separator Theorem for Minor-free Graphs in Linear Time
The planar separator theorem by Lipton and Tarjan states that any planar graph with $n$ vertices has a balanced separator of size $O(\sqrt{n})$ that can be found in linear time. …
10 events found.
Events
-
-
Room B332 IBS (기초과학연구원)
-
Daniel Dadush, A Strongly Polynomial Algorithm for Linear Programs with at Most Two Non-Zero Entries per Row or Column
Room B332 IBS (기초과학연구원)We give a strongly polynomial algorithm for minimum cost generalized flow, and hence for optimizing any linear program with at most two non-zero entries per row, or at most two …
-
-
Xiaofan Yuan (袁晓璠), Rainbow structures in edge colored graphs
Room B332 IBS (기초과학연구원)Let $G = (V, E)$ be a graph on $n$ vertices, and let $c : E \to P$, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in …
-
Seonghun Park (박성훈), Formalizing Flag Algebras in the Lean Theorem Prover
Room B332 IBS (기초과학연구원)Flag algebras are a mathematical framework introduced by Alexander Razborov in 2007, which has been used to resolve a wide range of open problems in extremal graph theory in the …
-
Marek Sokołowski, Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP
Room B332 IBS (기초과학연구원)In this talk, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP …
-
-
Chính T. Hoàng, Problems on graph coloring
Room B332 IBS (기초과학연구원)A k-coloring of a graph is an assignment of k colors to its vertices such that no two adjacent adjacent vertices receive the same color. The Coloring Problem is the …
-
Dario Cavallaro, Well-quasi-ordering Eulerian directed Graphs by (strong) Immersion
Room B332 IBS (기초과학연구원)Directed graphs prove to be very hard to tame in contrast to undirected graphs. In particular, they are not well-quasi-ordered by any known relevant inclusion relation, and are lacking fruitful …
-
József Balogh, Clique covers and decompositions of cliques of graphs
Room B332 IBS (기초과학연구원)Two related papers will be discussed: 1. In 1966, Erdős, Goodman, and Pósa showed that if $G$ is an $n$-vertex graph, then at most $\lfloor n^2/4 \rfloor$ cliques of $G$ …
-
Hidde Koerts, Characterizing large clique number in tournaments
Room B332 IBS (기초과학연구원)A backedge graph of a tournament $T$ with respect to a total ordering $\prec$ of the vertices of $T$ is a graph on $V(T)$ where $uv$ is an edge if …
-
Tung H. Nguyen, TBA
Room B332 IBS (기초과학연구원)