{"284621":{"#nid":"284621","#data":{"type":"event","title":"ARC Seminar\/DOS: Samuel Fiorini - Universit\u00e9 libre de Brussels (Brussels, Belgium).","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E Cut-dominant and forbidden minors\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract:\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EThe cut-dominant of a connected graph G is the polyhedron that corresponds to the problem of computing global min-cuts in G. Despite the fact that computing a global min-cut can be done in polynomial time, the geometry of the cut-dominant is far from being understood. We study graphs for which all facets of the corresponding cut-dominant have right-hand side at most a fixed integer k. These graphs form a minor-closed collection. We give a complete list of forbidden minors for k \u0026lt;= 2. This is then applied to the TSP to give a shorter proof of a classic result of Fonlupt and Naddef (Math. Prog., 1992) \u0026nbsp;that characterizes TSP-perfect graphs. This work in progress is joint with Kanstantsin Pashkovich (Brussels) and Michele Conforti (Padova).\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Samuel Fiorini will give a talk at the ARC Seminar"}],"uid":"27263","created_gmt":"2014-03-21 08:33:01","changed_gmt":"2017-04-13 21:22:54","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2014-03-26T17:00:00-04:00","event_time_end":"2014-03-26T18:00:00-04:00","event_time_end_last":"2014-03-26T18:00:00-04:00","gmt_time_start":"2014-03-26 21:00:00","gmt_time_end":"2014-03-26 22:00:00","gmt_time_end_last":"2014-03-26 22:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[{"id":"111051","name":"Algorithm and Randomness Center"},{"id":"4265","name":"ARC"},{"id":"6121","name":"DOS"},{"id":"109","name":"Georgia Tech"},{"id":"1808","name":"graduate students"},{"id":"14673","name":"theory"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[{"id":"78751","name":"Undergraduate students"},{"id":"78761","name":"Faculty\/Staff"},{"id":"174045","name":"Graduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:sebastian.pokutta@isye.gatech.edu\u0022\u003Esebastian.pokutta@isye.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}