OKlibrary  0.2.1.6
EliminationSequences.hpp File Reference

Plans tree decompositions via elimination sequences. More...

Go to the source code of this file.


Detailed Description

Plans tree decompositions via elimination sequences.

Todo:
GraphDecomposition::Treewidth_by_enumerating_elimination_sequences
  • Write tests.
  • Generalise it by using strategy objects.
Todo:
GraphDecomposition::Width_elimination_sequence
  • Extend it by computing also the tree decompositon.
  • Here it seems necessary that we make a local copy of the input graph, where each vertex in the copy has as property its associated vertex in the original graph (in this way we can change the copy, while the tree decomposition obtained referes to the original (unchanged) graph).
Todo:
Greedy strategy
  • Implement the greedy strategy for computing an elimination sequence.
  • Likely we achieve better performance when not going to the eye of the needle represented by the elimination sequence, but just taking as input a graph g with vertices and edges removable, and asking an algorithm visitor for the next vertex from the (remaining) graph --- the greedy algorithm then is realised by an algorithm visitor returning a vertex with minimum degree.

Definition in file EliminationSequences.hpp.