PermutationStrategy.h File Reference

Priority-queue-based node-elimination ordering for tree decomposition. More...

#include <boost/heap/fibonacci_heap.hpp>
#include "Graph.h"

Include dependency graph for PermutationStrategy.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	PermutationStrategy
	Node-elimination ordering strategy using a priority queue. More...
struct	PermutationStrategy::node_type
	Entry in the priority queue. More...

Detailed Description

Priority-queue-based node-elimination ordering for tree decomposition.

Originally taken and adapted from https://github.com/smaniu/treewidth

Computing an optimal tree decomposition is NP-hard in general. PermutationStrategy implements a greedy heuristic that eliminates nodes from a graph one at a time in the order of a priority determined by a node statistic (by default, current degree). The sequence of eliminated nodes defines an elimination ordering, and the cliques formed during elimination define the bags of the resulting tree decomposition.

The base class implements the min-degree heuristic. Subclasses can override compute_statistic() to implement other heuristics (e.g., min-fill, which counts the number of edges that would be added to the graph when the node is eliminated).

A Fibonacci heap is used so that recompute() (decrease-key after neighbours are updated) runs in amortised O(1) time.

Definition in file PermutationStrategy.h.