Campus Event Calendar: Valia Mitsou (11/20/2014 in E1 4/024)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

The computational complexity of two card games with theoretical applications

Valia Mitsou

Hokkaido University (Sapporo, Japan)

AG1 Mittagsseminar (own work)

AG 1, MMCI

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Thursday, 20 November 2014

13:00

30 Minutes

E1 4

024

Saarbrücken

Abstract

The main theme of this talk is card games that can be naturally reformulated as well-known graph-theoretic problems. In particular, we will focus on two different games: the game of SET, and the game of UNO. The objective of the former is to form sets of cards that match in a certain sense, while in the latter players need to discard their cards following a matching rule (for more details regarding the rules of the two games please visit the following websites: official website of SET (http://www.setgame.com/set/index.html), wikihow: how to play UNO (http://www.wikihow.com/Play-UNO).

We will describe connections of the two games with a number of different problems such as Multidimensional Matching, Set Packing, Edge Dominating Set, and Hamiltonian Path. These connections will help us show algorithmic as well as hardness results for variations of both games in the classical and the parameterized sense. The connections described are two-fold as our results will, in several cases, imply progress for the state of the art of the corresponding graph-theoretic problems.

This talk will include results from two different publications: "The computational complexity of the game of SET", joint with Michael Lampis, LATIN 2014, and "Parameterized Edge Hamiltonicity", joint with Michael Lampis, Kazuhisa Makino, and Yushi UNO, WG 2014.

Contact

Holger Dell

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Holger Dell, 11/18/2014 14:37
Holger Dell, 11/17/2014 14:10
Holger Dell, 11/17/2014 14:10 -- Created document.

Imprint / Impressum | Data Protection / Datenschutzhinweis