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
10 events found.
Seminars and Colloquiums
Akash Kumar, Random walks and Forbidden Minors
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how random walks helped make progress on algorithmic problems on planar graphs. In particular, I show how random walk based (i.e., spectral) approaches led to progress …
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 …
Raul Lopes, Temporal Menger and related problems
Room B332 IBS (기초과학연구원)A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability, i.e. sequence of adjacent edges whose appearing times are non-decreasing. Given a graph G and vertices s and t of G, Menger’s Theorem states that …
Brett Leroux, Expansion of random 0/1 polytopes
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every
Jun Gao, Number of (k-1)-cliques in k-critical graph
Room B332 IBS (기초과학연구원)We prove that for
Raphael Steiner, Congruence-constrained subdivisions in digraphs
Zoom ID: 869 4632 6610 (ibsdimag)I will present the short proof from that for every digraph F and every assignment of pairs of integers
Bjarne Schülke, A local version of Katona’s intersection theorem
Room B332 IBS (기초과학연구원)Katona's intersection theorem states that every intersecting family
Dömötör Pálvölgyi, C-P3O: Orientation of convex sets and other good covers
Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the …
Sebastian Wiederrecht, Killing a vortex
Room B332 IBS (기초과학연구원)The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that, for every