기초과학연구원 이산수학그룹
|
S
Sun
|
M
Mon
|
T
Tue
|
W
Wed
|
T
Thu
|
F
Fri
|
S
Sat
|
|---|---|---|---|---|---|---|
|
0 events,
|
0 events,
|
1 event,
-
In this talk, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the entries in the first row with integer coefficients. Using these conditions we show the invertibility of some family of circulant matrices with particular forms of … |
1 event,
-
The local connectivity |
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
For positive integers, |
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
For a graph |
1 event,
-
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 in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain … |
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
|
0 events,
|
0 events,
|
0 events,
|
0 events,
|
|
0 events,
|
0 events,
|
1 event,
-
In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with … |
1 event,
-
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 recently remained out of reach. Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that … |
0 events,
|
0 events,
|
0 events,
|