Approximation Algorithms for B 1-EPG Graphs.
Dror EpsteinMartin Charles GolumbicGila MorgensternPublished in: WADS (2013)
Keyphrases
- approximation algorithms
- undirected graph
- np hard
- special case
- worst case
- minimum cost
- network design problem
- vertex cover
- facility location problem
- approximation guarantees
- primal dual
- disjoint paths
- randomized algorithms
- set cover
- approximation ratio
- directed graph
- weighted graph
- np hardness
- constant factor
- spanning tree
- graph model
- graph structure
- graph matching
- connected components
- lower bound