기초과학연구원 이산수학그룹
|
S
Sun
|
M
Mon
|
T
Tue
|
W
Wed
|
T
Thu
|
F
Fri
|
S
Sat
|
|---|---|---|---|---|---|---|
|
0 events,
|
1 event,
-
We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order … |
0 events,
|
1 event,
-
We confirm a conjecture of Gartland and Lokshtanov : if for a hereditary graph class |
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers |
1 event,
-
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 … |
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
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 … |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
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 … |
0 events,
|
1 event,
-
A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every |
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
We prove that for |
1 event,
-
I will present the short proof from that for every digraph F and every assignment of pairs of integers |
0 events,
|
0 events,
|
0 events,
|