general.hpp File Reference

Plans for matchings in graphs. More...

Go to the source code of this file.


namespace  OKlib::Matchings

Matching algorithms for graphs (in the Boost sense)

namespace  OKlib

All components of the OKlibrary.

Detailed Description

Plans for matchings in graphs.

Update namespaces.
Literature and software review on matching algorithms
Concepts for bipartite graphs are needed.
First implementations
  • As a first simple algorithm, a matching problem is reduced to a network flow problem, so that the maximum flow algorithms from Boost can be used.
  • Hungarian method: Implement the basic direct algorithm for finding maximum matchings.
Injectivity constraints
  • For the 1-strong active clause-sets INJ(V,D) (see InjectivityConstraints/plans/InjectivityConstraints.hpp) an algorithm is needed for a bipartite graph finding out the set of edges which are not element of some maximum matching.
  • Concepts are then needed to employ such algorithms for implementing injectivity-constraints.
Online: We need also "online"-versions of these algorithms, allowing to remove some edges and recomputing the maximum matching respectively the set of unusable edges. Removing edges corresponds to applying some partial assignment; adding some edges then would correspond to backtracking steps.
Counting: We need (exact) algorithms for counting of perfect matchings
  • in bipartite graphs
  • in graphs
  • in general graphs
  • in hypergraphs
  • in general hypergraphs.

Direct implementations as well as translations to #SAT problems.

  • Efficient computations of the surplus of a bipartite graph.
  • Efficient decision whether the surplus is positive.

With these algorithms it can be decided whether a clause-set is matching-lean, etc.; see MatchingAutarkies/plans/MatchingAutarkies.hpp.

Correction: DONE Find the date in the cvs-logs for Matchings/plans/milestones.hpp (originally the first version was 0.0.1, but this was changed to 0.0.2, since there were already some more plans there).

Definition in file general.hpp.