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

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

## Classes

class | GeneralLowerBoundAlgorithm
| Generic lower bound algorithm on graphs. More...
class | MinorMinWidthReducer
class | MinorMinWidthCriterion
class | GreedyX
struct | FillInHeuristic
class | QuickBB
class | TreeDecompositionBuilder

## Public Types

typedef boost::graph_traits< UndirectedGraph >::vertex_descriptor | VertexType
typedef boost::graph_traits< UndirectedGraph >::adjacency_iterator | NeighbourIterator
typedef boost::graph_traits< UndirectedGraph >::vertex_iterator | VertexIterator
typedef std::pair< std::vector< Size >, Size > | EliminationOrder
typedef GeneralLowerBoundAlgorithm< MinorMinWidthCriterion, MinorMinWidthReducer > | MinorMinWidth
typedef GreedyX< FillInHeuristic > | GreedyFillIn

## Detailed Description

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

Definition at line 177 of file treeWidth.h.

## Member Typedef Documentation

## EliminationOrder

template<class UndirectedGraph>

typedef std::pair<std::vector<Size>, Size> BALL::TreeWidthImplementation< UndirectedGraph >::EliminationOrder

An EliminationOrder is a permutation of vertices of a graph which can be used to build a Fill-In-Graph. The TreeDecomposition of such a graph is a minimal Tree-Decomposition of the source graph, if the elimination order is perfect. first is the permutation of vertices, second is the tree width of the Three-Decomposition of such a Fill-In graph

Definition at line 191 of file treeWidth.h.

## GreedyFillIn

template<class UndirectedGraph>

typedef GreedyX<FillInHeuristic> BALL::TreeWidthImplementation< UndirectedGraph >::GreedyFillIn

An upperbound heuristic which computes an EliminationOrder, which can build a tree decomposition, and a treewidth of a given graph. The basic idea is to add as few as possible edges into the FillInGraph, because this should reduce the treewidth of the FillInGraph. Nevertheless, it's just a heuristic, so there is no guarantee, that the treewidth is minimal.

Exceptions

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

Definition at line 445 of file treeWidth.h.

## MinorMinWidth

template<class UndirectedGraph>

typedef GeneralLowerBoundAlgorithm<MinorMinWidthCriterion, MinorMinWidthReducer> BALL::TreeWidthImplementation< UndirectedGraph >::MinorMinWidth

Minor-Min-Width is a lowerbound algorithm for computing the treewidth. It contracts in each step a vertex u, which has minimum degree in graph, with a vertex v, which has a minimum degree in u's neighbourhood. The maximum of the minimum degrees is the lowerbound for the treewidth.

The basic idea behind this algorithm is:

- the treewidth of a graph is never lower than the treewidth of its minor
- the treewidth of a graph is never lower than the minimum degree of its vertices (because you can always find an optimal tree decomposition which contains a leaf, which has at least one vertex v, which isn't contained in the parents vertex set. For each edge of this vertex v, there must be a vertex in the leaf. So degree(v) is a minimal treewidth of this tree decomposition!)
  Exceptions

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

Definition at line 268 of file treeWidth.h.

## NeighbourIterator

template<class UndirectedGraph>

typedef boost::graph_traits<UndirectedGraph>::adjacency_iterator BALL::TreeWidthImplementation< UndirectedGraph >::NeighbourIterator

Definition at line 182 of file treeWidth.h.

## VertexIterator

template<class UndirectedGraph>

typedef boost::graph_traits<UndirectedGraph>::vertex_iterator BALL::TreeWidthImplementation< UndirectedGraph >::VertexIterator

Definition at line 183 of file treeWidth.h.

## VertexType

template<class UndirectedGraph>

typedef boost::graph_traits<UndirectedGraph>::vertex_descriptor BALL::TreeWidthImplementation< UndirectedGraph >::VertexType

Definition at line 181 of file treeWidth.h.