Loading...
Searching...
No Matches
BALL::TreeWidthImplementation< UndirectedGraph >::GreedyX< Criterion > Class Template Reference

`#include <BALL/DATATYPE/GRAPH/treeWidth.h>`

Inheritance diagram for BALL::TreeWidthImplementation< UndirectedGraph >::GreedyX< Criterion >:

## Public Member Functions

EliminationOrder | operator() (UndirectedGraph &original_graph)

## Additional Inherited Members

Public Types inherited from BALL::UnaryFunctor< UndirectedGraph, std::pair< std::vector< boost::graph_traits< UndirectedGraph::vertex_descriptor > >, Size > >
typedef std::pair< std::vector< boost::graph_traits< UndirectedGraph::vertex_descriptor > >, Size > | result_type
typedef UndirectedGraph | argument_type
typedef UndirectedGraph & | argument_reference
typedef const UndirectedGraph & | const_argument_reference
typedef UndirectedGraph * | argument_pointer
typedef const UndirectedGraph * | const_argument_pointer

## Detailed Description

template<class UndirectedGraph>
template<class Criterion>
class BALL::TreeWidthImplementation< UndirectedGraph >::GreedyX< Criterion >

Algorithm which can be extended to different upperbound heuristics which follow the same procedure: Finding a vertex v by a special criterium, insert this vertex in the elimination order and then eliminate it in the graph.

The basic idea is to build a Fill-In-Graph. Such a Fill-In-Graph can be produced by eliminating the vertices of a graph and adding the edges, which appear by eliminating, into the Fill-In-Graph. If the vertices were eliminated in the correct order, the tree decomposition of the Fill-In-Graph is also the optimal tree decomposition of the source graph. Otherwise, it's a tree decomposition with higher treewidth which can be used as upperbound. The order of eliminating is called EliminationOrder. Each GreedyX algorithm returns the EliminationOrder with the vertex permuation and the treewidth. This vertex permutation can be used to build a tree decomposition of the source graph.

Template Parameters

  Criterion | the criterium which chooses the next vertex to eliminate

Exceptions

  BALL::GRAPH::UnconnectedGraphException | if called on unconnected graphs

Definition at line 287 of file treeWidth.h.

## Member Function Documentation

## operator()()

template<class UndirectedGraph>
template<class Criterion>

EliminationOrder BALL::TreeWidthImplementation< UndirectedGraph >::GreedyX< Criterion >::operator() | ( | UndirectedGraph & | original_graph | ) |