OKlibrary  0.2.1.6
general.hpp File Reference

Plans for matchings in graphs. More...

Go to the source code of this file.

Namespaces

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.

Todo:
Update namespaces.
Todo:
Literature and software review on matching algorithms
Todo:
Concepts for bipartite graphs are needed.
Todo:
Relations
Todo:
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.
Todo:
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.
Todo:
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.
Todo:
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.

Todo:
Surplus:
  • 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.

Todo:
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.