Module graph_algo_ptas::algorithm::ptas

source · [−]
Expand description

Contains the main algorithm implementing the PTAS for planar graphs.

use graph_algo_ptas::generation::planar::generate;
use graph_algo_ptas::algorithm::ptas::ptas;
use graph_algo_ptas::algorithm::dynamic_programming::solve::DpProblem;

let graph = generate(100, None).to_pet_graph();
let sol = ptas(&graph, &DpProblem::max_independent_set(), 0.5);

Functions

ptas
Calculates an approximate solution for the given problem on the input graph. The input graph is expected to be planar.