{"72825":{"#nid":"72825","#data":{"type":"event","title":"ARC Colloquium: Laszlo Vegh , Eovtos Lorand University","body":[{"value":"\u003Cp\u003EAbstract:\u003C\/p\u003E\u003Cp\u003EIn the node-connectivity augmentation problem, we want to add a minimum number of new edges to an undirected graph to make it k-node-connected. The complexity of this question is still open, although the analogous questions of both directed and undirected edge-connectivity and directed node-connectivity augmentation are known to be polynomially solvable.\u003Cbr \/\u003E\u003Cbr \/\u003EIn my talk, I present a min-max formula and a polynomial time algorithm for the special case when the input graph is already (k-1)-connected. The formula has been conjectured by Frank and Jordan in 1994. I also give an overview of the other three augmentation problems. \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Augmenting undirected node-connectivity by one"}],"uid":"27263","created_gmt":"2011-11-16 12:44:51","changed_gmt":"2016-10-08 01:56:37","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2010-11-08T12:30:00-05:00","event_time_end":"2010-11-08T12:30:00-05:00","event_time_end_last":"2010-11-08T12:30:00-05:00","gmt_time_start":"2010-11-08 17:30:00","gmt_time_end":"2010-11-08 17:30:00","gmt_time_end_last":"2010-11-08 17:30:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003EElizabeth Ndongi\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}