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.