USRA Seminar - Jack Dippel

Tuesday, August 2, 2016 2:30 pm - 2:30 pm EDT (GMT -04:00)

Title: Min cost bridgeless subgraph of min degree 2 (bridgeless D2)

Speaker: Jack Dippel
Affiliation: University of Waterloo
Room: MC 6486

Abstract: In the bridgeless D2 problem we have a graph with nonnegative edge costs and the goal is to complete a min cost subgraph of degree at least 2 at every node that has no bridges (i.e. no cut edges.).

We discuss NP-hardness, LP relaxations and approximation algorithms.