Jaehoon Kim (김재훈), A resilience version of Pósa’s theorem
Room B232 IBS (기초과학연구원)Pósa's theorem states that any graph G whose degree sequence
10 events found.
Seminars and Colloquiums
Dennis Wong, Generating Gray codes and universal cycles for weak orders
Room B232 IBS (기초과학연구원)A weak order is a way to rank n objects where ties are allowed. Weak orders have applications in diverse areas such as linguistics, designing combination locks, and even in horse racing. In this talk, we present new and simple algorithms to generate Gray codes and universal cycles for weak orders.
Seog-Jin Kim (김석진), Online DP-coloring of graphs
Room B232 IBS (기초과학연구원)Online list coloring and DP-coloring are generalizations of list coloring that attracted considerable attention recently. Each of the paint number,
Casey Tompkins, Inverse Turán Problems
Room B232 IBS (기초과학연구원)For given graphs
Ilkyoo Choi (최일규), Flexibility of Planar Graphs
Room B232 IBS (기초과학연구원)Oftentimes in chromatic graph theory, precoloring techniques are utilized in order to obtain the desired coloring result. For example, Thomassen's proof for 5-choosability of planar graphs actually shows that two adjacent vertices on the same face can be precolored. In this vein, we investigate a precoloring extension problem formalized by Dvorak, Norin, and Postle named flexibility. Given a …
Paloma T. Lima, Graph Square Roots of Small Distance from Degree One Graphs
Zoom ID: 869 4632 6610 (ibsdimag)Given a graph class
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)
Akanksha Agrawal, Polynomial Kernel for Interval Vertex Deletion
Zoom ID: 869 4632 6610 (ibsdimag)Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k, such that G-S is an interval graph. A polynomial kernel for a parameterized problem is a polynomial time preprocessing algorithm that outputs an equivalent instance of the problem whose size is bounded by …
June Huh (허준이), Kazhdan-Lusztig polynomials of graphs and matroids
Room B232 IBS (기초과학연구원)I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon, Proudfoot, and Young that all zeros of the Kazhdan-Lusztig polynomial of a matroid lie on the negative real axis.
Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
Zoom ID: 869 4632 6610 (ibsdimag)Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a …