primal_dual.hpp file
Functions
-
template<typename Graph, typename C1, typename C2>auto min_vertex_cover_pd(const Graph& gra, C1& cover, const C2& weight) -> auto
- minimum weighted vertex cover problem
-
template<typename Graph, typename C1, typename C2>auto min_maximal_independant_set_pd(const Graph& gra, C1& indset, C1& dep, const C2& weight) -> auto
- minimum maximal independant set problem
Function documentation
template<typename Graph, typename C1, typename C2>
auto min_vertex_cover_pd(const Graph& gra,
C1& cover,
const C2& weight)
minimum weighted vertex cover problem
| Template parameters | |
|---|---|
| Graph | |
| C1 | |
| C2 | |
| Parameters | |
| gra in | |
| cover in/out | |
| weight in | |
| Returns | auto |
This function solves minimum vertex cover problem using primal-dual approximation algorithm:
template<typename Graph, typename C1, typename C2>
auto min_maximal_independant_set_pd(const Graph& gra,
C1& indset,
C1& dep,
const C2& weight)
minimum maximal independant set problem
| Template parameters | |
|---|---|
| Graph | |
| C1 | |
| C2 | |
| Parameters | |
| gra in | |
| indset | |
| dep | |
| weight in | |
| Returns | auto |
This function solves minimum maximal independant set problem using primal-dual approximation algorithm: