Module graph_algo_ptas::algorithm::dynamic_programming::solve

Contains data structures and algorithms for dynamic programming on tree decompositions.

use graph_algo_ptas::generation::erdos_renyi::generate_petgraph;
use graph_algo_ptas::algorithm::dynamic_programming::solve::dp_solve;
use graph_algo_ptas::algorithm::dynamic_programming::solve::DpProblem;

let graph = generate_petgraph(20, 0.1, None);
let sol = dp_solve(&graph, None, &DpProblem::max_independent_set());

Structs

DpProblem

Contains the neccessary information for solving a (hard) problem using dynamic programming on tree decompositions.

DpTableEntry

Represents a single entry in a dynamic programming table.

Enums

DpObjective

Used for differentiating between minimization and maximization problems.

Functions

dp_solve

Solves the given problem on the input graph using dynamic programming.

dp_solve_hashmap_graph

For convenience.

Type Definitions

DpTable

For each bag in the tree decomposition a table is calculated. Such a table is represented by HashMap.