problemreductions/models/graph/
mod.rs

1//! Graph problems.
2//!
3//! Problems whose input is a graph (optionally weighted):
4//! - [`MaximumIndependentSet`]: Maximum weight independent set
5//! - [`MaximalIS`]: Maximal independent set
6//! - [`MinimumVertexCover`]: Minimum weight vertex cover
7//! - [`MinimumDominatingSet`]: Minimum dominating set
8//! - [`MinimumFeedbackVertexSet`]: Minimum weight feedback vertex set in a directed graph
9//! - [`MaximumClique`]: Maximum weight clique
10//! - [`MaxCut`]: Maximum cut on weighted graphs
11//! - [`GraphPartitioning`]: Minimum bisection (balanced graph partitioning)
12//! - [`KColoring`]: K-vertex coloring
13//! - [`MaximumMatching`]: Maximum weight matching
14//! - [`TravelingSalesman`]: Traveling Salesman (minimum weight Hamiltonian cycle)
15//! - [`SpinGlass`]: Ising model Hamiltonian
16//! - [`BicliqueCover`]: Biclique cover on bipartite graphs
17
18pub(crate) mod biclique_cover;
19pub(crate) mod graph_partitioning;
20pub(crate) mod kcoloring;
21pub(crate) mod max_cut;
22pub(crate) mod maximal_is;
23pub(crate) mod maximum_clique;
24pub(crate) mod maximum_independent_set;
25pub(crate) mod maximum_matching;
26pub(crate) mod minimum_dominating_set;
27pub(crate) mod minimum_feedback_vertex_set;
28pub(crate) mod minimum_vertex_cover;
29pub(crate) mod spin_glass;
30pub(crate) mod traveling_salesman;
31
32pub use biclique_cover::BicliqueCover;
33pub use graph_partitioning::GraphPartitioning;
34pub use kcoloring::KColoring;
35pub use max_cut::MaxCut;
36pub use maximal_is::MaximalIS;
37pub use maximum_clique::MaximumClique;
38pub use maximum_independent_set::MaximumIndependentSet;
39pub use maximum_matching::MaximumMatching;
40pub use minimum_dominating_set::MinimumDominatingSet;
41pub use minimum_feedback_vertex_set::MinimumFeedbackVertexSet;
42pub use minimum_vertex_cover::MinimumVertexCover;
43pub use spin_glass::SpinGlass;
44pub use traveling_salesman::TravelingSalesman;