OKlibrary  0.2.1.6
BoundedTransversals_bv.cpp File Reference

Application for computing all size-bounded transversals of a hypergraph. More...

Go to the source code of this file.

Enumerations

enum  

Functions

int main (const int argc, const char *const argv[])

Detailed Description

Application for computing all size-bounded transversals of a hypergraph.

  • The hypergraph is read from standard input, in DIMACS format.
  • The output is the list of transversals, also in DIMACS format.
  • The role model is transversals_bvs in ComputerAlgebra/Hypergraphs/Lisp/Transversals/Bounded/MaintainingBound.mac.
  • To perform this computation requires (exactly) one parameter, of the form "=B".
  • This is a simple recursive search (by branching on vertices) for computing basically all minimal transversals of size at most B.
  • With an argument ">=B" (a lower bound), or with no argument (corresponding to ">=0"), minimum_transversals_lbbvs_hg in ComputerAlgebra/Hypergraphs/Lisp/Transversals/Bounded/MaintainingBound.mac is realised, i.e., incremental search.
  • So "=B" is used if the size of minimum transversals is known, while otherwise starting from a known lower bound the size of minimum transversals is computed by the algorithm.

Definition in file BoundedTransversals_bv.cpp.


Enumeration Type Documentation

anonymous enum

Definition at line 47 of file BoundedTransversals_bv.cpp.


Function Documentation

int main ( const int  argc,
const char *const  argv[] 
)

Definition at line 59 of file BoundedTransversals_bv.cpp.