Archive for the ‘KAIST Discrete Math Seminar’ Category

« Older Entries
Newer Entries »

Eunjung Kim, A polynomial-time algorithm for outerplanar diameter improvement

Tuesday, March 4th, 2014
A polynomial-time algorithm for outerplanar diameter improvement
Eunjung Kim
CNRS, LAMSADE, Paris, France
2014/05/26 Monday 4PM-5PM
Room 1409
The Outerplanar Diameter Improvement problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Kwang Ju Choi, Nearly planar graphs and graph minor obstructions for embedding on the spindle surface

Monday, March 3rd, 2014
Nearly planar graphs and graph minor obstructions for embedding on the spindle surface
Kwang Ju Choi
NIMS
2014/05/19 Monday 4PM-5PM
Room 1409
In this talk, we define nearly planar graphs, that is, graphs that are edgeless or have an edge whose deletion results in a planar graph. We show that all but finitely many graphs that are not nearly planar and do not contain one particular graph have a well-understood structure based on large Mobius ladders. D. Archdeacon and C. Bonnington proved that a cubic obstruction for near-planarity is the same as an obstruction for embedding on the spindle surface and they gave the topological obstruction set for cubic nearly planar graphs. Now, we are searching graph minor obstructions for embedding on the spindle surface. This is a joint work with Bogdan Oporowski and Guoli Ding.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Gena Hahn, Cops, robbers, infinite graphs and related problems

Sunday, March 2nd, 2014
Cops, robbers, infinite graphs and related problems
Gena Hahn
University of Montreal, Canada
2014/05/14 Wednesday 4PM-5PM
Room 1409
We briefly survey the game of cops-and-robbers on graphs and its variants in the fi nite case and then concenrate on in finite graphs, stressing the diff erence between the fi nite and the in finite. Along the way we show (time allowing) how to construct in finite vertex transitive graphs from any graphs and point out some strange properties of the construction. We also suggest several open problems, both fi nite and infi nite. The talk is based on work with A. Bonato, C.Tardif and R.E. Woodrow.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Michael Lampis, Parameterized Approximation Schemes using Graph Widths

Sunday, March 2nd, 2014
Parameterized Approximation Schemes using Graph Widths
Michael Lampis
Kyoto University, Japan
2014/05/13 Tuesday 4PM-5PM
Room 1409
A number of natural graph problems are known to be W-hard to solve exactly when parameterized by standard widths (treewidth or clique-width). At the same time, such problems are typically hard to approximate in polynomial time. In this talk we will present a natural randomized rounding technique that extends well-known ideas and can be used to obtain FPT approximation schemes for several such problems, evading both polynomial-time inapproximability and parameterized intractability bounds.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

Valia Mitsou, The computational complexity of the game of SET and its theoretical applications

Sunday, March 2nd, 2014
The computational complexity of the game of SET and its theoretical applications
Valia Mitsou
University of New York, USA
2014/05/12 Monday 4PM-5PM
Room 1409
The game of SET is a popular card game in which the objective is to form Sets (triplets of cards that match in a particular sense) using cards from a special deck. For more details regarding the game, please visit the official website: http://www.setgame.com/.
We analyze the computational complexity of some variations of the game of SET, presenting positive as well as hardness results in the classical and parameterized sense. Along the way, we make interesting connections of these generalizations of the game with other combinatorial problems, like Perfect Multi-Dimensional Matching, Set Packing, Independent Edge Dominating Set, and a two-player game played on graphs called Arc Kayles.

Tags:
Posted in 2014, KAIST Discrete Math Seminar | Comments Closed

« Older Entries
Newer Entries »